最值问题
题目背景
这不是一道难题,但需要一点数据结构的知识。至少,你需要先知道什么是“树”。
题目描述
给定一棵n个点的树,求无序点对<u,v>的数量,满足u到v的简单路径上边权最大值-边权最小值为k
格式
输入格式
第一行两个数n,k表示树的大小和要求的差值。
接下来n-1行,每行三个数u,v,w,表示读入一条带权的树边。
输出格式
一行一个整数表示答案。
样例
输入样例1
5 2
2 1 1
3 1 4
4 3 5
5 4 3
输出样例1
2
数据范围
15% \(1 \leq n \leq 5000\)
额外20% 树为一条链
额外10% 树上只有一个点度数>1
80% \(1 \leq n \leq 10^5\)
100% \(1 \leq n \leq 2×10^5\) \(1 \leq w \leq 10^9\)
时空限制
时间:1s
空间:128MB
样例解释
合法的点对为(3,5)和(1,5)
信息
- ID
- 1202
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 38
- 已通过
- 1
- 通过率
- 3%
- 被复制
- 1
- 上传者
相关
在下列比赛中: