시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB212657529619.603%

문제

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

파타야 인근 지역에는 N 개의 도시가 있고 N-1 개의 고속도로가 이 도시들을 연결하고 있다. 각 고속도로는 양방향이며 서로 다른 두 개의 도시를 연결한다. 각 고속도로의 길이는 킬로미터 단위로 나타내며 정수 값이다. 그리고 임의의 두 도시는 직접 고속도로로 연결되지 않더라도 단 하나의 경로에 의해 연결된다. 즉, 같은 도시를 두 번 이상 방문하지 않고 한 도시에서 출발하여 다른 도시에 도착하는 방법은 유일하다.

IOR 에 사용되는 경주코스는 출발 도시와 도착 도시가 서로 달라야 하며 길이는 정확하게 K 킬로미터인 경로이다. 그리고 충돌을 방지하기 위해 한 고속도로를 두 번 이상 사용하지 않는다. (따라서 한 도시도 두 번 이상 방문하지 않는다.) 또한 교통체증을 줄이기 위해 되도록 가장 작은 수의 고속도로를 사용하여 경주코스를 구성하려고 한다.

다음의 파라미터를 받는 best_path(N,K,H,L) 함수를 작성하라.

  • N – 도시의 수. 각 도시는 0 번부터 N-1 번까지 정수로 나타낸다.
  • K – 경주코스의 길이.
  • H – 각 고속도로를 나타내는 2 차원 배열. 고속도로 i (0 ≤ i < N-1)는 도시 H[i][0]와 도시 H[i][1]를 연결하는 도로이다.
  • L – 고속도로의 길이를 나타내는 1 차원 배열. 고속도로 i (0 ≤ i < N-1)의 길이는 L[i]이다.

배열 H 에 저장된 값은 0 이상 N-1 이하이다. 또한 배열 L 에 저장된 값은 0 이상 1 000 000 이하의 정수이다. 그리고 모든 도시들은 연결되어 있다.

당신이 작성한 함수는 길이가 K 인 경주코스 중에서 고속도로 수가 가장 작은 경주코스의 고속도로 수를 반환한다. 만약 길이가 K 인 경주코스가 없다면 -1 을 반환하라.

입력

첫째 줄에 N과 K가 주어진다. 둘째 줄부터 N-1개 줄에는 H[i][0], H[i][1], L[i]가 주어진다.

출력

best_path(N,K,H,L)가 리턴한 값을 출력한다.

서브태스크 1 (9점)

  • 1 ≤ N ≤ 100
  • 1 ≤ K ≤ 100
  • 고속도로들이 직선을 이룬다: 고속도로 i 는 ( 0 ≤ i < N-1) 도시 i 와 도시 i+1 을 연결한다

서브태스크 2 (12점)

  • 1 ≤ N ≤ 1 000
  • 1 ≤ K ≤ 1 000 000

서브태스크 3 (22점)

  • 1 ≤ N ≤ 200 000
  • 1 ≤ K ≤ 100

서브태스크 4 (57점)

  • 1 ≤ N ≤ 200 000
  • 1 ≤ K ≤ 1 000 000

예제 입력 1

4 3
0 1 1
1 2 2
1 3 4

예제 출력 1

2

그림 1

가능한 경주코스는 도시 0 에서 출발하여 도시 1 을 거쳐 도시 2 에 도착하는 코스이다. 이 코스의 총 길이는 1 km + 2 km = 3 km 이며 2 개의 고속도로를 사용한다. 이 코스가 최적의 코스이므로 best_path(N,K,H,L)는 2 를 반환해야 한다.

예제 입력 2

3 3
0 1 1
1 2 1

예제 출력 2

-1

그림 2

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

예제 입력 3

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

예제 출력 3

2

그림 3

이 경우 여러 개의 경주코스가 존재한다. 그 중 하나는 도시 6 에서 출발하여 도시 0 과 2 를 거쳐 도시 3 에 도착하는 코스이다. 또 다른 하나는 도시 10 에서 출발하여 도시 8 을 거쳐 도시 6 에 도착하는 코스이다. 두 코스 모두 길이가 12km 이지만 두 번째 코스는 2 개의 고속도로만 이용하며 이는 최적의 코스이다. 왜냐하면 한 개의 고속도로만 이용하는 코스가 없기 때문이다. 따라서 best_path(N,K,H,L)는 2 를 반환해야 한다.

채점 및 기타 정보

  • 예제는 채점하지 않는다.