TopCoder

User's AC Ratio

93.3% (14/15)

Submission's AC Ratio

81.8% (18/22)

Tags

Description

給定一棵樹,如果把樹上的某一個節點及其所連的邊移除,我們會得到若干棵樹。例如下左圖為原始的樹,移除節點 $2$ 之後就會變成如中間那張圖,而若移除節點 $1$ 則會變成如右邊那張圖。

對於給定的一棵樹,我們定義拔除節點 $x$ 的慘度為「拔除節點 $x$ 後,形成的若干棵樹分別的節點數量中的最大值」。舉例來說,上左圖拔除節點 $2$ 之後,形成 $2$ 棵樹,節點數量分別是 $1$ 和 $3$,其中最大者為 $3$,因此該樹拔除節點 $2$ 的慘度為 $3$。同理,該樹拔除節點 $1$ 的慘度為 $2$。

對於一棵樹,我們定義所有點當中,拔除它的慘度最小的點為「重心」。現在給你一棵樹,請你找出它的「重心」。

Input Format

第一行為一個正整數 $T$,$T \le 10$,表示共有幾筆測試資料。
每筆測試資料的第一行為一個正整數 $N$,表示這棵樹共有 $N$ 個節點,編號為 $0$ 到 $N-1$。接續 $N-1$ 行,每行兩個整數 $a,b$,表示節點 $a$ 和節點 $b$ 有一條邊相連。

  • 對於 $40\%$ 的測試資料,$N \le 100$
  • 對於 $100\%$ 的測試資料,$2 \le N \le 10 ^ 5$、輸入為合法的一棵樹

Output Format

對於每筆測試資料輸出一行,包含一個整數,即為這棵樹的重心的編號,若有多個,請輸出編號較小的。

Sample Input 1

1
5
0 1
1 2
1 4
2 3

Sample Output 1

1

Hints

範例即為題目中的圖片,

  • 拔除節點 $0$ 的慘度為 $4$、
  • 拔除節點 $1$ 的慘度為 $2$、
  • 拔除節點 $2$ 的慘度為 $3$、
  • 拔除節點 $3$ 的慘度為 $4$、
  • 拔除節點 $4$ 的慘度為 $4$。

拔除節點 $1$ 的慘度最小,因此答案為 $1$。

Problem Source

NEOJ Problem 293

Subtasks

No. Testdata Range Constraints Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 2
2 1000 65536 65536 3
3 1000 65536 65536 4
4 1000 65536 65536 5
5 1000 65536 65536 6
6 1000 65536 65536 7
7 1000 65536 65536 8
8 1000 65536 65536 9
9 1000 65536 65536 10