242 . 樹重心

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

75.0% (3/4)

Tags

ioicamp ioicamp-2020

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

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
Submit
Back to Top