A21612.Race

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

输入格式

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

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

注意:点从 00 开始编号

输出格式

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

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

输入输出样例

  • 输入#1

    4 3
    0 1 1
    1 2 2
    1 3 4

    输出#1

    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

首页