P16063 [CSPro 24] 极差路径

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。 众所周知，西西艾弗岛是一个旅游胜地，但是由于兴建机场，西西艾弗岛最近的财务状况有点紧张。

为了从游客手中获取更多的经济利润，岛上仅有的三个小学生小 C、小 S 和小 P 建立了 $n$ 个景点，编号依次从 $1$ 到 $n$。编号为 $i$ 的景点是第 $i$ 个被修建的。由于越到后期经费越是不足，所以编号更大的景点通常更令人不满意——方便起见，假定编号为 $i$ 的景点的令人不满意程度是 $i$。 有些景点之间修有双向可通行的道路，但是出于减少经费的考虑，他们只修了能使得所有景点连通的最少数量的道路，从而这些景点和其间的道路形成一棵树的结构。 对于每个游客而言，由于只修了 $n - 1$ 条道路，所以他只能沿着树上的边参观，并且由于他不可能重复参观一个景点，所以他的游览路径一定是树上的一条简单路径。 现在西西艾弗岛希望制定一些推荐游览路径，但并非所有树上的路径都是合意的，因为这条路径上的景点令人不满意程度的极差可能过大，使游客产生这些景点质量不稳定的错觉。由于最开始的景点和最后的景点令人印象比较深刻，所以游客通常会把游览路径上的景点和这两个景点作比较。因此，最令人不满意的景点不能比这两个景点差太多，最优秀的景点也不能比这两个景点优秀太多。 具体来说，一条从 $x$ 到 $y$ 的游览路径（记作 $(x, y)$）是推荐的，当且仅当下式成立： $$ \min\{x, y\} - k_1 \leq \min P(x, y) \leq \max P(x, y) \leq \max\{x, y\} + k_2 $$ 其中 $P(x, y)$ 表示一条从 $x$ 出发到达 $y$ 的简单路径上的点的令人不满意程度的数值的集合（包括 $x$ 和 $y$，也就是 $x$ 到 $y$ 的简单路径上的点的编号的集合），$\min S$ 和 $\max S$ 分别表示集合 $S$ 中的最小和最大值，$k_1, k_2$ 是西西艾弗岛经过数次尝试后选取的两个给定的参数，保证 $k_1, k_2 \geq 0$。 特别的，容易验证 $x = y$ 时 $(x, y)$ 总是推荐的。 现在西西艾弗岛想知道，一共有多少树上的简单路径作为游览路径是被推荐的？这里我们认为 $(x, y)$ 和 $(y, x)$ 是同一条路径。

从标准输入读入数据。 第一行输入三个非负整数 $n, k_1, k_2$。 接下来 $n - 1$ 行，每行两个正整数 $x, y$ 表示树上的一条边。

输出到标准输出。 输出一行一个非负整数表示答案。

### 样例 1 解释 容易验证 $(1, 1), (1, 4), (1, 5), (1, 3), (2, 2), (2, 4), (2, 5), (2, 3), (3, 3), (4, 4), (4, 5), (5, 5)$ 都是推荐的游览路径，因此答案是 $12$。 ### 样例 2 见题目录下的 `2.in` 与 `2.ans`。 ### 样例 3 见题目录下的 `3.in` 与 `3.ans`。 ### 样例 4 见题目录下的 `4.in` 与 `4.ans`。 ### 样例 5 见题目录下的 `5.in` 与 `5.ans`。 ### 样例 6 见题目录下的 `6.in` 与 `6.ans`。 ### 样例 7 见题目录下的 `7.in` 与 `7.ans`。 ### 样例 8 见题目录下的 `8.in` 与 `8.ans`。 ### 子任务 | 测试点 | $n \leq$ | $k_1$ | $k_2$ | 树的形态 | 堆性质 | |:------:|:--------:|:-----:|:-----:|:--------:|:------:| | 1 | $5,000$ | $\leq n$ | $\leq n$ | $A_3$ | 无 | | 2 | ^ | ^ | ^ | ^ | ^ | | 3 | ^ | ^ | ^ | ^ | ^ | | 4 | $5 \times 10^5$ | $= 0$ | $= 0$ | $A_1$ | 有 | | 5 | ^ | ^ | ^ | ^ | 无 | | 6 | ^ | $\leq n$ | ^ | ^ | 有 | | 7 | ^ | ^ | ^ | ^ | 无 | | 8 | ^ | ^ | $\leq n$ | ^ | 有 | | 9 | ^ | ^ | ^ | ^ | 无 | | 10 | ^ | $= 0$ | $= 0$ | $A_2$ | ^ | | 11 | ^ | $\leq n$ | ^ | ^ | ^ | | 12 | ^ | ^ | $\leq n$ | ^ | ^ | | 13 | ^ | $= 0$ | $= 0$ | $A_3$ | 有 | | 14 | ^ | ^ | ^ | ^ | 无 | | 15 | ^ | ^ | ^ | ^ | ^ | | 16 | ^ | ^ | ^ | ^ | ^ | | 17 | ^ | $\leq n$ | ^ | ^ | 有 | | 18 | ^ | ^ | ^ | ^ | 无 | | 19 | ^ | ^ | ^ | ^ | ^ | | 20 | ^ | ^ | ^ | ^ | ^ | | 21 | ^ | ^ | $\leq n$ | ^ | 有 | | 22 | ^ | ^ | ^ | ^ | ^ | | 23 | ^ | ^ | ^ | ^ | 无 | | 24 | ^ | ^ | ^ | ^ | ^ | | 25 | ^ | ^ | ^ | ^ | ^ | 对于 $100\%$ 的数据，$1\le n\le 5\times 10^5,0\le k1,k2\le n$，保证输入的 $n−1$ 条边一定构成一棵树。 树的形态： - $A1$：树是一条链； - $A2$：存在一个度数为 $n−1$ 的点； - $A3$：树的形态无特殊性质。 堆性质：若取编号为 $1$ 的点为根，则除 $1$ 号点外，每个点的编号都比其父节点的编号大。 请注意答案可能的取值范围。