TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

75.0% (3/4)

Tags

Description

給定一棵 N 個點的有根樹,點以 1N 作為編號,點 1 為樹根。

現在,對於每個點 i,請求出以 i 為根的子樹中,樹重心的編號們。

一個 n 個點的樹中的一個點 v 被稱為樹重心代表若移除點 v 後,所有連通塊的大小皆不超過 n2

Input Format

輸入第一行有一個正整數 N,代表樹的大小。

接下來 N1 行每行有兩個正整數 ui,vi,代表節點 ui 到節點 vi 之間有一條邊。

  • 1N2×105
  • 1ui,viN
  • 保證給定的圖為一棵樹

Output Format

輸出 N 行,第 i 行輸出以點 i 為根的子樹的樹重心們。如果你在一行要輸出很多個數字,請按照編號小到大的順序輸出。

Sample Input 1

8
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

Hints

Problem Source

IOICamp 2020 Day2 pD

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~30 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2