#T2159. 定长路径 II(Fixed-Length Paths II)

定长路径 II(Fixed-Length Paths II)

链接: https://cses.fi/problemset/task/2081

板块: Tree Algorithms

时限: 1.00 s | 内存: 512 MB

题目描述

给定一棵包含 nn 个节点的树,你的任务是统计边数至少为 k1k_1 且至多为 k2k_2 的不同路径的数量。

输入

第一行包含三个正整数 nn、k1k_1 和 k2k_2:节点数和路径长度范围。节点编号为 1,2,…,n1,2,\ldots,n。

接下来有 n−1n-1 行描述边。每行包含两个整数 aa 和 bb:节点 aa 与 bb 之间有一条边。

输出

输出一个整数:路径的数量。

数据范围

1≤k1≤k2≤n≤2⋅1051 \le k_1 \le k_2 \le n \le 2 \cdot 10^5 1≤a,b≤n1 \le a,b \le n

样例输入

5 2 3
1 2
2 3
3 4
3 5

样例输出

6