P16828 [AFOI 2025] E. Clearance Sale

I often do clearance sales in the past.

Now the candies in the candy shop are almost sold out. There are only $n$ candies left, scattered in the warehouse of the candy shop. The warehouse can be seen as a tree structure with $n$ storage rooms. Each storage room has one candy, and there are $n-1$ bidirectional roads between storage rooms. Any two storage rooms are reachable from each other. For magical reasons, the deliciousness of the candy in storage room $i$ is exactly $i$. Little R now wants to buy two more candies, but because the candies in the warehouse are too messy, Little X asks him to pick them up by himself. Little R gets a map of the warehouse, and his walking strategy is as follows: 1. He will choose any storage room to start walking. 2. After arriving at a storage room, he will walk to any adjacent storage room that he has not visited yet. If there is none, he will go back to the storage room where he was before he first arrived at this storage room. If that storage room does not exist, he ends his walk. During the walk, he may choose to eat the candy in a storage room when he passes through that storage room for the **first time**, but he will make this choice **exactly twice**, no more and no less. As everyone knows, eating a more delicious candy first and then a less delicious candy makes people feel unhappy. So Little R wants to know how many walking-and-eating plans will make him unhappy, that is, how many walking-and-eating plans make the deliciousness of the first candy he eats greater than that of the second candy. Note that **if the eating plan is the same but the walking plan is different, they are still considered two different plans**. Since the answer may be large, you only need to output the result modulo $10^9+7$.

The first line contains an integer $n$, representing the number of storage rooms. The next $n-1$ lines each contain two integers $u,v$, representing a road connecting storage room $u$ and storage room $v$.

Output one integer in one line, representing the answer modulo $10^9+7$.

**【Constraints】** For all testdata, it is guaranteed that: $2 ≤ n ≤ 5 × 10^5 $. ::cute-table{tuack} | Test Point ID | $n\le$ | Special Property | Score | Subtask ID | | :-: | :-: | :-: |:--: | :--:| | $1 \sim 2$ | $20$ | None | $5$ | $0$ | | ^ | ^ | ^ | ^ | ^ | | $3 \sim6$ | $100$ | ^ | $10$ | $1$ | | ^ | ^ | ^ | ^ | ^ | | ^ | ^ | ^ | ^ | ^ | | ^ | ^ | ^ | ^ | ^ | | $7$ | $1000$ | $A$ | $5$ | $2$ | | $8$ | ^ | $B$ | $5$ | $3$ | | $9$ | ^ | $C$ | $5$ | $4$ | | $10 \sim 11$ | ^ | None | $15$ | $5$ | | $12$ | $10^5$ | $A$ | $5$ | $6$ | | $13$ | ^ | $B$ | $5$ | $7$ | | $14$ | ^ | $C$ | $5$ | $8$ | | $15 \sim 16$ | ^ | None | $20$ | $9$ | | $17 \sim 20$ | $5\times10^5$ | None | $20$ | $10$ | Special Property $A$: It is guaranteed that the distance between any two storage rooms is at most $2$. Special Property $B$: It is guaranteed that the number of roads connected to any storage room is at most $2$. Special Property $C$: It is guaranteed that there exists a simple path such that, for any storage room, the minimum distance from it to all points on this simple path is at most $1$. **Test point bundling is enabled within each subtask**. That is, contestants must pass all test points in a subtask to get the score for that subtask. Translated by ChatGPT 5