P14666 Wander Problem

Given a rooted tree with $n$ nodes, rooted at node $1$. Now let's start the wander from node $s$, abiding by the following rules: - If we have gone to $u$'s parent $f$ from $u$, **delete** the edge $(u,f)$ **immediately**. - When $u$ has no neighbor, the wander stops. For two plans $A,B$, we call they are **essentially different** **only** when the sets of nodes they pass through are different. It can be proven that if plan $A,B$ are the same, the numbers of step that their token are also the same. Compute the sum of the lengths of all **essentially different** walks, modulo $10^9+7$.

The first line contains two integers $n$ and $s$. The next $n-1$ lines each contains two positive integers $u$ and $v$, representing an edge $(u,v)$.

A single integer, the sum of the lengths modulo $10^9+7$.

### Example explanation Consider all possible **essentially different** paths: - $5,3,2,1$; - $5,3,7,3,2,1$; - $5,3,7,3,2,4,2,1$; - $5,3,2,4,2,1$; - $5,6,5,3,2,1$; - $5,6,5,3,7,3,2,1$; - $5,6,5,3,2,4,2,1$; - $5,6,5,3,7,3,2,4,2,1$; The sum is $48$. ### Data Volume and Conventions **This problem is divided into subtasks.** Your score in a subtask is the minimum score across all its test cases. **This problem uses subtask dependencies.** You will not receive the score for a subtask unless you achieve full points on all its dependent subtasks.  | Subtask | $n \le$ | Special Properties | Score | Dependencies | |:-----:|:-----:|:-----:|:-----:|:-----:| | $1$ | $5$ | none | $10$ | none | | $2$ | $10^3$ | none | $25$ | $1$ | | $3$ | $10^6$ | A | $5$ | none | | $4$ | $10^6$ | B | $10$ | none | | $5$ | $10^6$ | C | $20$ | none | | $6$ | $10^6$ | none | $30$ | $1,2,3,4,5$ | 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$. Special property C: $s=1$. For all of the cases, $1 \le s \le n \le 10^6$.