P4827 [CTT Mutual Test 2011] Crash’s Civilization World

Crash has recently become obsessed with a game called Civilization V. In this game, players can build and develop their own countries, communicate with other countries through diplomacy, or conquer them through war. Now Crash already owns a country with $n$ cities. These cities are connected by roads. Since building roads costs money, Crash only built $n-1$ roads to connect these cities, but it is guaranteed that there is a path between any two cities. In the game, Crash needs to choose one city as the capital of his country. Choosing the capital requires considering many indicators, and one of them is: $$S(i) = \sum_{j = 1}^{n}{\rm dist}(i, j) ^ k$$ Here, $S(i)$ denotes the indicator value of the $i$-th city, ${\rm dist}(i, j)$ is the minimum number of roads that must be traveled from city $i$ to city $j$, and $k$ is a constant positive integer. So Crash gives you a simple task: given the roads between the cities, for each city output its indicator value. Since the value may be very large, you only need to output it $\bmod\ 10007$.

The first line contains two positive integers $n$ and $k$. Then there are $n-1$ lines. Each line contains two positive integers $u, v$ ($1\le u, v\le n$), indicating that there is a road connecting city $u$ and city $v$. These roads are guaranteed to satisfy the requirements of the problem.

Output $n$ lines in total, each with one positive integer. The integer on the $i$-th line represents the indicator value of the $i$-th city $\bmod\ 10007$.

For $20\%$ of the testdata, $n\le 5000$, $k\le 30$. For $50\%$ of the testdata, $n\le 5\times 10^4$, $k\le 30$. For $100\%$ of the testdata, $1\le n\le 5\times 10^4$, $1\le k\le 150$. Translated by ChatGPT 5