A2523. Race
编程题
省选/NOI-
知识点
题目描述
给一棵树，每条边有权。求一条简单路径，权值和等于 $k$，且边的数量最小。
输入格式
第一行包含两个整数 $n,k$，表示树的大小与要求找到的路径的边权和。
接下来 $n-1$ 行，每行三个整数 $u_i,v_i,w_i$，代表有一条连接 $u_i$ 与 $v_i$，边权为 $w_i$ 的无向边。
**注意：点从 $0$ 开始编号**。
接下来 $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$。