IOI 2011 day1 2- 경주(Race) > 문제은행 : 정보올림피아드&알고리즘




2527 : 경주(Race)

제한시간
3000 ms   
메모리제한
256 MB   
해결횟수
11 회   
시도횟수
60 회   

문제

IOI를 개최하는 파타야시는 경주대회인 IOR2011도 함께 개최하며 이를 위해 가장 적합한 경주코스를 찾고 있다.



파타야 인근 지역에는 N개의 도시가 있고 N-1개의 고속도로가 이 도시들을 연결하고 있다. 

각 고속도로는 양방향이며 서로 다른 두 개의 도시를 연결한다. 

각 고속도로의 길이는 킬로미터 단위로 나타내며 정수 값이다. 

그리고 임의의 두 도시는 직접 고속도로로 연결되지 않더라도 단 하나의 경로에 의해 연결된다. 

즉, 같은 도시를 두 번 이상 방문하지 않고 한 도시에서 출발하여 다른 도시에 도착하는 방법은 유일하다.



IOR에 사용되는 경주코스는 출발 도시와 도착 도시가 서로 달라야 하며 길이는 정확하게 K 킬로미터인 경로이다. 

그리고 충돌을 방지하기 위해 한 고속도로를 두 번 이상 사용하지 않는다. (따라서 한 도시도 두 번 이상 방문하지 않는다.) 

또한 교통체증을 줄이기 위해 되도록 가장 작은 수의 고속도로를 사용하여 경주코스를 구성하려고 한다.

 

 

[예제 설명]



 

 

가능한 경주코스는 도시 0 에서 출발하여 도시 1 을 거쳐 도시 2 에 도착하는 코스이다. 

이 코스의 총 길이는 1 km + 2 km = 3 km 이며 2 개의 고속도로를 사용한다.


코스가 최적의 코스이므로 best_path(N,K,H,L)는 2 를 반환해야 한다.

 

 


 

이 경우 가능한 경주코스가 없으므로 best_path(N,K,H,L)는 -1 을 반환해야 한다.

 

 

 



이 경우 여러 개의 경주코스가 존재한다. 

그 중 하나는 도시 6 에서 출발하여 도시
0 과 2 를 거쳐 도시 3 에 도착하는 코스이다. 

또 다른 하나는 도시 10 에서 출발하여
도시 8 을 거쳐 도시 6 에 도착하는 코스이다. 

두 코스 모두 길이가 12km 이지만 두
번째 코스는 2 개의 고속도로만 이용하며 이는 최적의 코스이다. 

왜냐하면 한 개의
고속도로만 이용하는 코스가 없기 때문이다. 

따라서 best_path(N,K,H,L)는 2 를
반환해야 한다.
 

 


입력형식

입력의 첫줄에 도시의 수 N(1≤N≤200,000)과 경주코스의 길이 K(1≤K≤1,000,000)가 입력된다.
그 다음 줄부터 N-1개의 각 줄에 도시 Hi와 도시 Hj (0<=Hi, Hj<=N-1)연결하는 고속도로의 길이 L(0<=L<=1,000,000) 이 차례로 들어온다.


출력형식

출력은 한 줄로 이루어지는데, 길이가 K인 경주코스 중에서 고속도로 수가 가장 적은 경주코스의 고속도로 수를 출력한다. 

만약 길이가 K인 경주코스가 없다면 -1을 출력한다.


입력 예

4 3
0 1 1
1 2 2
1 3 4

출력 예

2

입력 예

3 3
0 1 1
1 2 1

출력 예

-1

입력 예

11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7

출력 예

2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP