263 . 樹重心
TopCoder
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
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 |