CSES2081 固定长度路径 II
#CS2081. 固定长度路径 II
固定长度路径 II
题目背景
翻译自 CSES-2081 题。
题目描述
给定一个包含 n 个节点的树，您的任务是计算路径长度在 k1k_1k1 和 k2k_2k2 之间的不同路径的数量，即路径包含至少 k1k_1k1 条边且最多 k2k_2k2 条边。
输入格式
第一行包含三个整数 n, k1k_1k1 和 k2k_2k2：树的节点数、路径的最小边数 k1k_1k1 和最大边数 k2k_2k2。节点编号为 1,2,…,n1,2,…,n1,2,…,n。
接下来有 n−1n−1n−1 行，每行包含两个整数 a 和 b：表示节点 a 和节点 b 之间有一条边。
输出格式
输出一个整数：路径长度在 k1k_1k1 到 k2k_2k2 之间的路径的数量。
样例
5 2 3
1 2
2 3
3 4
3 5
6
说明/提示
1≤k1≤k2≤n≤2⋅1051 \leq k_1 \leq k_2 \leq n \leq 2 \cdot 10^51≤k1≤k2≤n≤2⋅105；