最值问题

最值问题

题目背景

这不是一道难题,但需要一点数据结构的知识。至少,你需要先知道什么是“树”。

题目描述

给定一棵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
上传者