題目

一張地圖上有n個城市，城市和城市之間有且只有一條道路相連：要么直接相連，要么通過其它城市中轉(zhuǎn)相連（可中轉(zhuǎn)一次或多次）。城市與城市之間的道路都不會成環(huán)。

當切斷通往某個城市 i 的所有道路后，地圖上將分為多個連通的城市群，設該城市i的聚集度為DPi（Degree of Polymerization），DPi = max（城市群1的城市個數(shù)，城市群2的城市個數(shù)，…城市群m 的城市個數(shù)）。

請找出地圖上DP值最小的城市（即找到城市j，使得DPj = min(DP1,DP2 … DPn))

提示：如果有多個城市都滿足條件，這些城市都要找出來（可能存在多個解）

提示：DPi的計算，可以理解為已知一棵樹，刪除某個節(jié)點后；生成的多個子樹，求解多個子數(shù)節(jié)點數(shù)的問題。

輸入描述：

每個樣例：第一行有一個整數(shù)N，表示有N個節(jié)點。1 <= N <= 1000。

接下來的N-1行每行有兩個整數(shù)x，y，表示城市x與城市y連接。1 <= x,? y <= N

輸出描述：

輸出城市的編號。如果有多個，按照編號升序輸出。

示例1? ?輸入輸出示例僅供調(diào)試，后臺判題數(shù)據(jù)一般不包含示例

輸入

5

1 2

2 3

3 4

4 5

輸出

3

說明

輸入表示的是如下地圖：

對于城市3，切斷通往3的所有道路后，形成2個城市群[（1，2），（4，5）]，其聚集度分別都是2。DP3 = 2。

對于城市4，切斷通往城市4的所有道路后，形成2個城市群[（1，2，3），（5）]，DP4 = max（3，1）= 3。

依次類推，切斷其它城市的所有道路后，得到的DP都會大于2，因為城市3就是滿足條件的城市，輸出是3。

示例2? ?輸入輸出示例僅供調(diào)試，后臺判題數(shù)據(jù)一般不包含示例

輸入

6

1 2

2 3

2 4

3 5

3 6

輸出

2 3

說明

將通往2或者3的所有路徑切斷，最大城市群數(shù)量是3，其他任意城市切斷后，最大城市群數(shù)量都比3大，所以輸出2 3。

Java 實現(xiàn)：https://renjie.blog.csdn.net/article/details/127973417

Python實現(xiàn)：https://renjie.blog.csdn.net/article/details/130732664

C++ 實現(xiàn)：https://renjie.blog.csdn.net/article/details/127156708

JavaScript實現(xiàn)：https://renjie.blog.csdn.net/article/details/130732680

C實現(xiàn)：https://renjie.blog.csdn.net/article/details/129190260