← 返回题目列表

Codeforces · 293/E

E. 关闭顶点

中文机器翻译题面 查看原题

你有一个由 n 个顶点组成的加权树。每条边都有一个非负权重。树的任意两个顶点之间的路径长度就是该路径中的边数。路径的权重是它包含的所有边的总权重。

如果两个顶点之间存在长度至多为 l 的路径并且它们之间存在权重至多为 w 的路径,则两个顶点是接近的。计算顶点 v、u (v < u) 对的数量,使得顶点 v 和 u 接近。

输入

第一行包含三个整数 n、l 和 w (1 ≤ n ≤ 105、1 ≤ l ≤ n、0 ≤ w ≤ 109)。接下来的 n - 1 行包含树边的描述。第 i 行包含两个整数 pi、wi (1 ≤ pi < (i + 1), 0 ≤ wi ≤ 104),这意味着第 i 条边连接顶点 (i + 1) 和 pi,权重为 wi。

以某种方式考虑从 1 到 n 索引的树顶点。

输出

打印一个整数 — 接近对的数量。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

4 4 6
1 3
1 4
1 3

输出 #1

4

输入 #2

6 2 17
1 3
2 5
2 13
1 6
5 9

输出 #2

9