P9357 "SiR-1" Lighthouse

Given a tree with $n$ nodes, each node has a weight $w_i$, initially $0$. The initial score is $s=0$. Perform $m$ operations. In each operation, choose a node $u$, add to $s$ the size of the connected component of nodes with the same weight that contains $u$ (that is, suppose we keep only the nodes whose weight equals $w_u$, and the edges connecting two nodes whose weights both equal $w_u$; then the contribution to the score is the size of the connected component containing $u$ at this time. Note that this does not actually delete any nodes or edges from the tree), and then increase $w_u$ by $1$. For all $n^m$ possible sequences of operations, compute the sum of their scores $s$, modulo $10^9+7$.

The first line contains two positive integers, denoting $n,m$. The next $n-1$ lines each contain two positive integers, denoting the two endpoints $u,v$ of an edge.

Output one integer, the result modulo $10^9+7$.

For all data, it holds that $1\leq n\leq 1000$, $1\leq m\leq 10^5$, $1\leq u,v\leq n$, and the input is guaranteed to be a tree. - Subtask 0 (5 pts): $n,m\le 7$. - Subtask 1 (20 pts): $n,m\le 10$. - Subtask 2 (15 pts): $n,m\le 50$. - Subtask 3 (15 pts): $n,m\le 100$. - Subtask 4 (15 pts): $n\le 50$. - Subtask 5 (15 pts): the tree is a chain. - Subtask 6 (15 pts): no special restrictions. This problem also enables subtask dependencies. Specifically: + For subtask $i(i \in [1, 3])$, it depends on subtasks $0 \sim (i - 1)$. + For subtask $4$, it depends on subtasks $0 \sim 2$. + For subtask $6$, it depends on subtasks $0 \sim 5$. # Input Format # Output Format Translated by ChatGPT 5