该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P4149 [IOI 2011] Race

题目描述

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

输入格式

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

接下来 $n-1$ 行，每行三个整数 $u_i,v_i,w_i$，代表有一条连接 $u_i$ 与 $v_i$，边权为 $w_i$ 的无向边。

注意：点从 $0$ 开始编号。

输出格式

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

如果不存在这样的路径，输出 $-1$。

输入输出样例 #1

输入 #1

4 3
0 1 1
1 2 2
1 3 4

输出 #1

2

说明/提示

对于 $100\%$ 的数据，保证 $1\leq n\leq 2\times10^5$，$0\leq k,w_i\leq 10^6$，$0\leq u_i,v_i<n$。