#P4149. [IOI2011] Race

[IOI2011] Race

题目描述

给一棵树,每条边有权。求一条简单路径,权值和等于 kk,且边的数量最小。

输入格式

第一行包含两个整数 n,kn,k,表示树的大小与要求找到的路径的边权和。

接下来 n1n-1 行,每行三个整数 ui,vi,wiu_i,v_i,w_i,代表有一条连接 uiu_iviv_i,边权为 wiw_i 的无向边。

注意:点从 00 开始编号

输出格式

输出一个整数,表示最小边数量。

如果不存在这样的路径,输出 1-1

4 3
0 1 1
1 2 2
1 3 4
2

提示

对于 100%100\% 的数据,保证 1n2×1051\leq n\leq 2\times10^50k,wi1060\leq k,w_i\leq 10^60ui,vi<n0\leq u_i,v_i<n