P16063 [CSPro 24] Range Path

The testdata on Luogu are only for non-official communication and are not official testdata. Official judging link: . As everyone knows, Xixiaifu Island is a tourist attraction, but due to the construction of an airport, Xixiaifu Island has been under some financial pressure recently.

To obtain more economic profit from tourists, the only three elementary school students on the island, Little C, Little S, and Little P, built $n$ scenic spots, numbered from $1$ to $n$ in order. Spot $i$ is the $i$-th one built. Since funding becomes more insufficient later on, scenic spots with larger numbers are usually more unsatisfying. For convenience, assume that the degree of unsatisfaction of spot $i$ is $i$. Between some scenic spots, there are bidirectional roads. However, to reduce costs, they only built the minimum number of roads that makes all scenic spots connected, so the scenic spots and the roads form a tree. For each tourist, since there are only $n - 1$ roads, they can only travel along the edges of the tree. Also, since they cannot visit the same scenic spot twice, their tour route must be a simple path on the tree. Now Xixiaifu Island wants to create some recommended tour routes, but not all paths on the tree are desirable, because the range of unsatisfaction degrees along the path may be too large, giving tourists the impression that the quality of these scenic spots is unstable. Since the first and last scenic spots leave a deeper impression, tourists usually compare the scenic spots on the route with these two spots. Therefore, the most unsatisfying spot cannot be much worse than these two spots, and the best spot cannot be much better than these two spots. Specifically, a tour path from $x$ to $y$ (denoted as $(x, y)$) is recommended if and only if the following holds: $$ \min\{x, y\} - k_1 \leq \min P(x, y) \leq \max P(x, y) \leq \max\{x, y\} + k_2 $$ Here, $P(x, y)$ denotes the set of unsatisfaction-degree values of the nodes on the simple path starting from $x$ and reaching $y$ (including $x$ and $y$, i.e., the set of node indices on the simple path from $x$ to $y$). $\min S$ and $\max S$ denote the minimum and maximum values in a set $S$, respectively. $k_1, k_2$ are two given parameters chosen by Xixiaifu Island after several trials, and it is guaranteed that $k_1, k_2 \geq 0$. In particular, it is easy to verify that when $x = y$, $(x, y)$ is always recommended. Now Xixiaifu Island wants to know: how many simple paths on the tree are recommended as tour routes in total? Here we consider $(x, y)$ and $(y, x)$ to be the same path.

Read input from standard input. The first line contains three non-negative integers $n, k_1, k_2$. The next $n - 1$ lines each contain two positive integers $x, y$, indicating an edge of the tree.

Write output to standard output. Output one line containing a non-negative integer representing the answer.

### Explanation for Sample 1 It is easy to verify that $(1, 1), (1, 4), (1, 5), (1, 3), (2, 2), (2, 4), (2, 5), (2, 3), (3, 3), (4, 4), (4, 5), (5, 5)$ are all recommended tour paths, so the answer is $12$. ### Sample 2 See `2.in` and `2.ans` under the problem directory. ### Sample 3 See `3.in` and `3.ans` under the problem directory. ### Sample 4 See `4.in` and `4.ans` under the problem directory. ### Sample 5 See `5.in` and `5.ans` under the problem directory. ### Sample 6 See `6.in` and `6.ans` under the problem directory. ### Sample 7 See `7.in` and `7.ans` under the problem directory. ### Sample 8 See `8.in` and `8.ans` under the problem directory. ### Subtasks | Test Point | $n \leq$ | $k_1$ | $k_2$ | Tree Shape | Heap Property | |:----------:|:--------:|:-----:|:-----:|:----------:|:-------------:| | 1 | $5,000$ | $\leq n$ | $\leq n$ | $A_3$ | None | | 2 | ^ | ^ | ^ | ^ | ^ | | 3 | ^ | ^ | ^ | ^ | ^ | | 4 | $5 \times 10^5$ | $= 0$ | $= 0$ | $A_1$ | Yes | | 5 | ^ | ^ | ^ | ^ | None | | 6 | ^ | $\leq n$ | ^ | ^ | Yes | | 7 | ^ | ^ | ^ | ^ | None | | 8 | ^ | ^ | $\leq n$ | ^ | Yes | | 9 | ^ | ^ | ^ | ^ | None | | 10 | ^ | $= 0$ | $= 0$ | $A_2$ | ^ | | 11 | ^ | $\leq n$ | ^ | ^ | ^ | | 12 | ^ | ^ | $\leq n$ | ^ | ^ | | 13 | ^ | $= 0$ | $= 0$ | $A_3$ | Yes | | 14 | ^ | ^ | ^ | ^ | None | | 15 | ^ | ^ | ^ | ^ | ^ | | 16 | ^ | ^ | ^ | ^ | ^ | | 17 | ^ | $\leq n$ | ^ | ^ | Yes | | 18 | ^ | ^ | ^ | ^ | None | | 19 | ^ | ^ | ^ | ^ | ^ | | 20 | ^ | ^ | ^ | ^ | ^ | | 21 | ^ | ^ | $\leq n$ | ^ | Yes | | 22 | ^ | ^ | ^ | ^ | ^ | | 23 | ^ | ^ | ^ | ^ | None | | 24 | ^ | ^ | ^ | ^ | ^ | | 25 | ^ | ^ | ^ | ^ | ^ | For $100\%$ of the data, $1 \le n \le 5 \times 10^5$, $0 \le k1, k2 \le n$, and it is guaranteed that the $n - 1$ input edges form a tree. Tree shapes: - $A1$: the tree is a chain. - $A2$: there exists a node with degree $n - 1$. - $A3$: the tree has no special property. Heap property: if node $1$ is chosen as the root, then for every node except node $1$, its index is greater than its parent’s index. Please note the possible range of the answer. Translated by ChatGPT 5