給定一棵樹,如果把樹上的某一個節點及其所連的邊移除,我們會得到若干棵樹。例如下左圖為原始的樹,移除節點 $2$ 之後就會變成如中間那張圖,而若移除節點 $1$ 則會變成如右邊那張圖。
對於給定的一棵樹,我們定義拔除節點 $x$ 的慘度為「拔除節點 $x$ 後,形成的若干棵樹分別的節點數量中的最大值」。舉例來說,上左圖拔除節點 $2$ 之後,形成 $2$ 棵樹,節點數量分別是 $1$ 和 $3$,其中最大者為 $3$,因此該樹拔除節點 $2$ 的慘度為 $3$。同理,該樹拔除節點 $1$ 的慘度為 $2$。
對於一棵樹,我們定義所有點當中,拔除它的慘度最小的點為「重心」。現在給你一棵樹,請你找出它的「重心」。
第一行為一個正整數 $T$,$T \le 10$,表示共有幾筆測試資料。
每筆測試資料的第一行為一個正整數 $N$,表示這棵樹共有 $N$ 個節點,編號為 $0$ 到 $N-1$。接續 $N-1$ 行,每行兩個整數 $a,b$,表示節點 $a$ 和節點 $b$ 有一條邊相連。
對於每筆測試資料輸出一行,包含一個整數,即為這棵樹的重心的編號,若有多個,請輸出編號較小的。
範例即為題目中的圖片,
拔除節點 $1$ 的慘度最小,因此答案為 $1$。
NEOJ Problem 293
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 |