YZOJ P3924 [IOI2011]Race
时间限制：2000MS 内存限制：131072KB
难度：\(7.0\)
-
题目描述
给一棵树，每条边有权。
求一条简单路径，权值和等于 \(K\) ，且经过边的数量最小。
\(N \leq 200000, K \leq 1000000\) 。
-
输入格式
第一行 两个整数 \(n\)，\(k\) 。
第 \(2\)~\(n\) 行 每行三个整数，表示一条无向边的两端和权值（注意点的编号从 \(0\) 开始）。
-
输出格式
一个整数，表示最小边数量。
如果不存在这样的路径，输出 \(-1\) 。
-
样例输入
|
1 2 3 4 |
4 3 0 1 1 1 2 2 1 3 4 |
-
样例输出
|
1 |
2 |