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 |