對於給定的一棵樹，我們定義拔除節點 x 的慘度為「拔除節點 x 後，形成的若干棵樹分別的節點數量中的最大值。」。舉例來說，上左圖拔除節點 2 之後，形成 2 棵樹，節點數量分別是 1 和 3，其中最大者為 3，因此該樹拔除節點 2 的慘度為 3。同理，該樹拔除節點 1 的慘度為 2。
一棵樹，我們定義所有點當中，拔除它的慘度最小的點為「重心」。
現在給你一棵樹，請你找出它的「重心」。
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 100005;
int N;
vector <int> g[maxn];
int cost[maxn]; //慘度
int dfs(int now, int pre){
//tot: 以now為root的子樹size
int tot = 1, ret = 0;
// now下方的子樹
for (auto nxt: g[now]){
if (nxt != pre){
ret = dfs(nxt, now);
tot += ret;
cost[now] = max(cost[now], ret);
}
}
// now頭上的子樹
cost[now] = max(cost[now], N - tot);
return tot;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int T, a, b;
cin >> T;
while (T--){
cin >> N;
for (int i = 0; i < N; i++){
cost[i] = 0;
g[i].clear();
}
for (int i = 0; i < N-1; i++){
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(0, -1); //將0當作root
int mn = 0x7FFFFFFF;
int ans = -1;
for (int i = 0; i < N; i++){
if (cost[i] < mn){
mn = cost[i];
ans = i;
}
}
cout << ans << "\n";
}
return 0;
}
