YZOJ P3924 [IOI2011]Race

YZOJ P3924 [IOI2011]Race

时间限制:2000MS      内存限制:131072KB

难度:\(7.0\)

  • 题目描述

给一棵树,每条边有权。

求一条简单路径,权值和等于 \(K\) ,且经过边的数量最小。

\(N \leq 200000, K \leq 1000000\) 。

  • 输入格式

第一行 两个整数 \(n\),\(k\) 。

第 \(2\)~\(n\) 行 每行三个整数,表示一条无向边的两端和权值(注意点的编号从 \(0\) 开始)。

  • 输出格式

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

如果不存在这样的路径,输出 \(-1\) 。

  • 样例输入

  • 样例输出

 

 

 

Source: BZOJ 2599…