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


 

 

 

因为本题 \(K\) 较小,所以可能会有其他做法。

记 \(ans_i\) 为满足条件(权值和为 \(K\)),并且经过边数为 \(i\) 的点对的个数。

正贡献就是 \(+1\) ,消去重复答案就是 \(-1\) 。

然后就是一个裸的点分治

使用双指针时注意有 \(0\) 边权!!!

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注