Description

Given a rooted tree with root $1$, define a “nasty set” of the tree as a set such that for any two elements in the set, there is no ancestor-descendant relationship between them.

Define the “nasty index” of a nasty set as the sum of the values of all elements in the set. You are asked to compute the sum of the nasty indices of all nasty sets of the given tree, modulo $100{,}000{,}007$.

But this problem is too hard, so we consider a simplified version.

Because the node numbering is closely related to its nasty index, we will additionally give an integer $T$: when $T = 1$, the value (nasty index contribution) of node $i$ is $i$; when $T = 0$, the value of every node is $1$.

Input Format

The first line contains two integers $n$ and $T$, meaning the tree has $n$ nodes.

The next $n - 1$ lines each contain two integers $x$ and $y$, meaning there is an edge connecting $x$ and $y$.

Output Format

Output one integer, the answer.

5 0
1 2
2 3
2 4
1 5

16

Hint

Sample Explanation:

The $10$ sets are $\{1\},\{2\},\{3\},\{4\},\{5\},\{2,5\},\{3,4\}, \{3,5\},\{3,4,5\},\{4,5\}$.

Constraints and Notes

This problem uses bundled multiple test points.

• For $30\%$ of the points, $n \le 15$.
• For another $20\%$ of the points, $n \le 10^6$, $T = 0$.
• For $100\%$ of the data, $n \le 10^6$, $T \le 1$.

To help you understand the statement, here is the mathematical definition of a nasty set:

Let a nasty set be $A$. Then:

• $\forall i\in A$, there does not exist a node $j$ such that $j$ lies on the simple path from $i$ to the root, and $j \in A$. Here $i, j \in V$, and $V$ is the vertex set of the tree.

Translated by ChatGPT 5