P15446 「IXOI R1」BABABoy

A and B are playing a game on a tree. Specifically, you are given a tree $T$ rooted at node $1$. B starts the game from the root. In each round, he must choose to move to one of the children of the current node. He has no knowledge about the structure of the tree, which means he only knows the information about the children of the current node. A starts from any leaf node and in each round, A can move to any leaf node. A knows the structure of the tree as well as that B starts from the root node. During the game, he doesn't know the position of B. But before each round begins, he can use a skill to know where B is. Now the two start the game. In each round, the process is as follows: - A decides whether to use the skill to know the position of B. - A and B move at the same time. - If the node at which B stays is a leaf, then: if A is at the same node, A wins; otherwise B wins. The goal of A is to minimize the number of times using skills while maximizing the probability of winning. The goal of B is to maximize the probability of winning. A and B are extremely intelligent, and both of them employ the optimal strategy. Both A and B are aware of each other's situations and the game rules, and they also know that the other one is aware of their situations and the game rules as well. That is to say, the game rules and the situations of both parties are common knowledge to both parties. Calculate the expected number of times that A uses the skill, and print it modulo $10^9+7$. **Note**: If you are not familiar with the relevant knowledge of Nash equilibrium, you can assume that each time B will randomly choose one of the child nodes with equal probability.

The first line contains a positive integer $n$: the number of nodes of the tree. Next $n-1$ lines, each contains two integers $u$ and $v$, representing an edge $(u,v)$ on the tree.

Output one line, a single integer, representing the expected number of times that A uses the skill modulo $10^9+7$.

### Example Explanation One of A's optimal strategies is to use the skill at the beginning of the second round to check B's position and determine whether B is at node $2$ or node $3$. If B is at node $2$, then A should randomly choose one of nodes $4$ or $5$ to wait, and the winning probability is $\frac{1}{2}$. If B is at node $3$, then A should wait at node $6$, the expected number of skill uses is $1$. It can be proved that no better strategy exists. ### Constraints **This problem uses bundled testing.** | Subtask Id | $n\le $ |Special property|Points| | :----------: | :----------: | :----------: | :----------: | | $0$ | $10$ | No | $10$ | | $1$ | $10^3$ | No | $30$ | $2$ | $10^6$ | A | $10$ | | $3$ | $10^6$ | B | $10$ | | $4$ | $10^6$ | No | $40$ | Special property A: $\forall i\in[1,n),u_i=1$。 Special property B: $\forall i\in[1,n),u_i=i,v_i=i+1$。 For all data, it is guaranteed that: $2\le n\le 10^6$ and the given graph is a tree.