你有一个由 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