[R28D]树上路径 - 代码源竞赛平台

时空限制

2S/512M

题目描述

给定一棵由 $n$ 个节点组成的树，节点编号为 $1$ 到 $n$，其中 $1$ 号节点是根。树中的每条边都有一个边权 $w$。

我们需要你找出树中有多少个有序点对 $(u, v)$，满足以下两个条件：

1. 节点 $u$ 是节点 $v$ 的祖先（一个节点也是它自己的祖先）。
2. 从 $u$ 到 $v$ 的简单路径上所有边的权值之和恰好为 $K$。

格式

输入格式

第一行包含两个整数 $n$ 和 $K$，分别表示树的节点数和目标路径和。

接下来 $n-1$ 行，每行包含三个整数 $u, v, w$，表示节点 $u$ 和节点 $v$ 之间存在一条权值为 $w$ 的边。

保证给定的图是一棵树。

输出格式

输出一个整数，表示满足条件的点对 $(u, v)$ 的总数量。

样例

样例输入 #1

5 3
1 2 3
1 3 1
3 4 2
3 5 5

样例输出 #1

2

样例解释 #1

满足路径和为 $3$ 的祖先-后代点对 $(u, v)$ 如下：

1. 点对 $(1, 2)$：路径为 $1 \to 2$，路径和为 $3$。
2. 点对 $(1, 4)$：路径为 $1 \to 3 \to 4$，路径和为 $1 + 2 = 3$。

总共有 $2$ 个满足条件的点对。

数据规模

对于 $40\%$ 的数据，$1 \leq n \leq 1000$。

对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^5$，$1 \le u, v \le n$，$-10^9 \le w \le 10^9$，$0 \le K \le 5 \times 10^{15}$。保证给出的是一棵树。