751 . 樹重心

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

apcsc apcsc-graph

Description

將樹上的某個點移除後，樹將分成若干個子樹，定義其中最小化最大子樹的點為樹重心。現給一棵樹，請求其樹重心。

Input Format

輸入第一行是一個正整數 $N$ 表示樹的節點數。

接著有 $N-1$ 行每行空白分開的兩個數 $u,v$，代表樹上的邊。

輸入保證 $1\le N\le 10^ 5$，$0\le u,v < N$，且邊集構成一棵樹。

Output Format

假設樹有 $c$ 個重心，由小到大輸出 $c$ 行，每行包含一個整數，代表樹的重心位置。

Sample Input 1

5
0 1
0 2
2 4
3 0

Sample Output 1

0

Sample Input 2

4
0 1
1 2
2 3

Sample Output 2

1
2

Hints

Problem Source

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
Submit
Back to Top