Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LQDRACE - Race (IOI 2011)


Kết hợp với IOI, thành phố Pattaya sẽ tổ chức cuộc đua: Olympic quốc tế về đua tốc độ (IOR) 2011.
Là nhà tổ chức, chúng ta phải tìm ra vòng đua tốt nhất cho cuộc thi tốc độ này. 
Ở vùng Pattaya-Chonburi, có N thành phố được nối với nhau bởi mạng gồm N-1 đường cao tốc. Mỗi đường cao tốc đều cho phép đi theo cả hai chiều nối hai thành phố phân biệt và có độ dài đo bởi kilomet là số nguyên. Ngoài ra có đúng một đường đi giữa cặp hai thành phố bất kỳ. Nghĩa là, có đúng một cách đi từ một thành phố này đến một thành phố khác dọc theo dãy các đường cao tốc không qua bất cứ thành phố nào quá một lần.
IOR có qui tắc đặc biệt đòi hỏi vòng đua phải dài đúng K kilomet, bắt đầu và kết thúc ở hai thành phố phân biệt. Rõ ràng là không có đường cao tốc (và vì thế cũng không có thành phố) nào có thể được sử dụng quá một lần trên vòng đua để ngăn ngừa đụng độ. Để cực tiểu ảnh hưởng đến giao thông, vòng đua phải chứa một số ít nhất đường cao tốc có thể.
Yêu cầu:
Bạn hãy cho biết số lượng đường cao tốc nhỏ nhất trên vòng đua hợp qui tắc có độ dài đúng bằng K. Nếu không tìm được vòng đua như vậy, kết quả sẽ là -1.
Dữ liệu vào:
- Dòng đầu ghi số N, K.
- N-1 dòng tiếp theo mỗi dòng ghi 3 số u, v, l - đường cao tốc nối thành phố u và v, độ dài l (l <= 10^6).
Dữ liệu ra:
- 1 số nguyên duy nhất là kết quả của bài toán.
Giới hạn:
- 1 ≤ N ≤ 2 * 10^5
- 1 ≤ K ≤ 10^6
Ví dụ:
Input:
4 3
0 1 1
1 2 2
1 3 4
Output:
2
Input:
3 3 
0 1 1
1 2 1
Output:
-1
Input:
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
Output
2


Kết hợp với IOI, thành phố Pattaya sẽ tổ chức cuộc đua: Olympic quốc tế về đua tốc độ (IOR) 2011.

Là nhà tổ chức, chúng ta phải tìm ra vòng đua tốt nhất cho cuộc thi tốc độ này. 

Ở vùng Pattaya-Chonburi, có N thành phố được nối với nhau bởi mạng gồm N-1 đường cao tốc. Mỗi đường cao tốc đều cho phép đi theo cả hai chiều nối hai thành phố phân biệt và có độ dài đo bởi kilomet là số nguyên. Ngoài ra có đúng một đường đi giữa cặp hai thành phố bất kỳ. Nghĩa là, có đúng một cách đi từ một thành phố này đến một thành phố khác dọc theo dãy các đường cao tốc không qua bất cứ thành phố nào quá một lần.

IOR có qui tắc đặc biệt đòi hỏi vòng đua phải dài đúng K kilomet, bắt đầu và kết thúc ở hai thành phố phân biệt. Rõ ràng là không có đường cao tốc (và vì thế cũng không có thành phố) nào có thể được sử dụng quá một lần trên vòng đua để ngăn ngừa đụng độ. Để cực tiểu ảnh hưởng đến giao thông, vòng đua phải chứa một số ít nhất đường cao tốc có thể.


Yêu cầu:

Bạn hãy cho biết số lượng đường cao tốc nhỏ nhất trên vòng đua hợp qui tắc có độ dài đúng bằng K. Nếu không tìm được vòng đua như vậy, kết quả sẽ là -1.


Dữ liệu vào:

- Dòng đầu ghi số N, K.

- N-1 dòng tiếp theo mỗi dòng ghi 3 số u, v, l - đường cao tốc nối thành phố u và v, độ dài l (l <= 10^6).

Dữ liệu ra:

- 1 số nguyên duy nhất là kết quả của bài toán.


Giới hạn:

- 1 ≤ N ≤ 2 * 10^5

- 1 ≤ K ≤ 10^6


Ví dụ:

Input:

4 3

0 1 1

1 2 2

1 3 4

Output:

2


Input:

3 3 

0 1 1

1 2 1

Output:

-1


Input:

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

Output

2

 


Được gửi lên bởi:Tmbao
Ngày:2012-10-14
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:IOI 2011

hide comments
2018-08-25 16:08:28
Game la` de
2017-08-03 17:46:48
ád

Last edit: 2017-08-04 17:04:01
2012-12-09 14:29:11 Tmbao
P/s: Các bạn code bài này bằng C++ nên chú ý nếu duyệt cây bằng đệ quy có thể bị Runtime error (tràn stack) những test lớn

Last edit: 2012-12-10 16:31:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.