P10912 [Lanqiao Cup 2024 National B] Counting Stars

Xiaoming is counting stars on a tree. This tree has $n$ nodes $1, 2, \cdots, n$. He defines a subgraph $G$ on the tree to be a star if and only if $G$ satisfies all of the following: 1. $G$ is a tree. 2. There exists a node in $G$ whose degree is $|V_G| - 1$, where $|V_G|$ denotes the number of nodes contained in this subgraph. Two stars are considered different if and only if their node sets $V_G$ are not exactly the same. Xiaoming wants to know how many different stars in this tree have a number of nodes within the interval $[L, R]$. Output the answer modulo $1000000007$.

The input has a total of $n + 1$ lines. The first line contains a positive integer $n$. The next $n - 1$ lines each contain two positive integers, representing an edge of the tree. The $(n + 1)$-th line contains two positive integers $L, R$.

Output a total of $1$ line, containing one integer representing the answer.

**Sample Explanation.** There are $5$ stars containing $3$ nodes, and their node sets are $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 2, 5\}$, $\{2, 4, 5\}$, $\{1, 3, 6\}$. There is $1$ star containing $4$ nodes, and its node set is $\{1, 2, 4, 5\}$. **Constraints.** For $20\%$ of the testdata, it is guaranteed that $n \le 20$. For $100\%$ of the testdata, it is guaranteed that $n \le 10^5$, $1 \le L \le R \le n$. Translated by ChatGPT 5