242 . 樹重心
TopCoder
Tags
Description
給定一棵 $N$ 個點的有根樹，點以 $1$ 到 $N$ 作為編號，點 $1$ 為樹根。
現在，對於每個點 $i$，請求出以 $i$ 為根的子樹中，樹重心的編號們。
一個 $n$ 個點的樹中的一個點 $v$ 被稱為樹重心代表若移除點 $v$ 後，所有連通塊的大小皆不超過 $\frac{n}{2}$。
Input Format
輸入第一行有一個正整數 $N$，代表樹的大小。
接下來 $N - 1$ 行每行有兩個正整數 $u_i, v_i$，代表節點 $u_i$ 到節點 $v_i$ 之間有一條邊。
- $1 \leq N \leq 2 \times 10^ 5$
- $1 \leq u_i, v_i \leq N$
- 保證給定的圖為一棵樹
Output Format
輸出 $N$ 行，第 $i$ 行輸出以點 $i$ 為根的子樹的樹重心們。如果你在一行要輸出很多個數字，請按照編號小到大的順序輸出。
Sample Input 1
8
1 2
2 8
8 6
6 7
1 4
4 3
4 5
1 2
2 8
8 6
6 7
1 4
4 3
4 5
Sample Output 1
1 2
6 8
3
4
5
6 7
7
6
6 8
3
4
5
6 7
7
6
Hints
Problem Source
IOICamp 2020 Day2 pD
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~30 | 無額外限制 | 100 |