P16828 [AFOI 2025] E.清仓甩卖

我常常甩卖过去。

现在糖果店里的糖果已经快卖完了，只有 $n$ 颗还散落在糖果店的仓库中。仓库可以视为一个树形结构，有 $n$ 个库房，每个库房中有一颗糖果，库房之间有 $n-1$ 条双向道路可以行走，并且任意两个库房之间可以互相到达。由于神奇的原因，第 $i$ 号库房中的糖果的美味度恰好就是 $i$。小 R 现在想要再买两颗糖果，但由于仓库里的糖果太乱了，小 X 让他自己去取。小 R 拿到了仓库的地图，他的行走策略如下： 1. 他会任意选择一个库房开始行走。 2. 到达一个库房后，他会走向与这个库房相连的任意一个还未被他走过的库房，如果没有就退回他第一次到达这个库房前所在的库房，如果这个库房不存在则结束行走。 在行走的过程中，他可能会在他**第一次**走过某个库房时选择吃掉这个库房里的糖果，但只会做出这个选择**两次**，不会多也不会少。 由于众所周知，先吃一个更美味的糖果再吃一个不那么美味的糖果会让人感到不爽，所以小 R 想要知道，有多少种行走以及吃糖果的方案会让他不爽，也就是，有多少种行走以及吃糖果的方案会让他吃的第一颗糖果美味度大于第二颗。注意，**如果选择吃糖果的方案相同但行走的方案不同，也会被视为两种不同的方案**。由于答案可能较大，你只需要求出答案对 $10^9+7$ 取模后的结果。

第一行一个整数 $n$，代表库房个数。 接下来 $n-1$ 行，每行两个整数 $u,v$ 代表一条连接 $u$ 号库房和 $v$ 号库房的道路。

一行一个整数，表示答案对 $10^9+7$ 取模后的结果。

**【数据范围】** 对于所有的测试数据，保证：$2 ≤ n ≤ 5 × 10^5 $。 ::cute-table{tuack} | 测试点编号 | $n\le$ | 特殊性质 | 分值 | 子任务编号 | | :-: | :-: | :-: |:--: | :--:| | $1 \sim 2$ | $20$ | 无 | $5$ | $0$ | | ^ | ^ | ^ | ^ | ^ | | $3 \sim6$ | $100$ | ^ | $10$ | $1$ | | ^ | ^ | ^ | ^ | ^ | | ^ | ^ | ^ | ^ | ^ | | ^ | ^ | ^ | ^ | ^ | | $7$ | $1000$ | $A$ | $5$ | $2$ | | $8$ | ^ | $B$ | $5$ | $3$ | | $9$ | ^ | $C$ | $5$ | $4$ | | $10 \sim 11$ | ^ | 无 | $15$ | $5$ | | $12$ | $10^5$ | $A$ | $5$ | $6$ | | $13$ | ^ | $B$ | $5$ | $7$ | | $14$ | ^ | $C$ | $5$ | $8$ | | $15 \sim 16$ | ^ | 无 | $20$ | $9$ | | $17 \sim 20$ | $5\times10^5$ | 无 | $20$ | $10$ | 特殊性质 $A$：保证任意两个库房距离不超过 $2$。 特殊性质 $B$：保证连接任意一个库房的道路数量不超过 $2$。 特殊性质 $C$：保证存在一条简单路径，使得任意一个库房到这条简单路径上所有点距离的最小值不超过 $1$。 **本题子任务内开启测试点捆绑**，即选手需要通过一个子任务内的所有测试点才能获得该测试点的分数。