A21612.Race
省选/NOI-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
给一棵树,每条边有权。求一条简单路径,权值和等于 k,且边的数量最小。
输入格式
第一行包含两个整数 n,k,表示树的大小与要求找到的路径的边权和。
接下来 n−1 行,每行三个整数 ui,vi,wi,代表有一条连接 ui 与 vi,边权为 wi 的无向边。
注意:点从 0 开始编号。
输出格式
输出一个整数,表示最小边数量。
如果不存在这样的路径,输出 −1。
输入输出样例
输入#1
4 3 0 1 1 1 2 2 1 3 4
输出#1
2
说明/提示
对于 100% 的数据,保证 1≤n≤2×105,0≤k,wi≤106,0≤ui,vi<n。