【題意】：給你一棵樹，去掉一個結(jié)點后，得到的平衡值是指分開的所有子樹中結(jié)點數(shù)的最大值，求去掉哪個點，平衡值最小。
【題解】：dfs一次，把無向樹變成有向樹。順便統(tǒng)計以每個結(jié)點為根的樹的結(jié)點數(shù)，記為cnt[].
那么點u的平衡值 balance[u] = max(n - cnt[u], max(cnt[v])),其中 v 為 u 的兒子。
最后，ans = { u | balance[u] = min(balance[])};
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 using namespace std;
8 #define pb push_back
9 #define maxn 20050
10 vector<int> vec[maxn];
11 int n;
12 int balance[maxn], cnt[maxn];
13
14 void dfs(int u, int fa) {
15 int size = vec[u].size();
16 cnt[u] = 1;
17 int tmp = 0;
18 for(int i = 0; i < size; i++) {
19 int v = vec[u][i];
20 if(v == fa) continue;
21 dfs(v, u);
22 cnt[u] += cnt[v];
23 tmp = max(cnt[v], tmp);
24 }
25 balance[u] = max(tmp, n - cnt[u]);
26 }
27
28 int main() {
29 int T, u, v;
30 scanf("%d", &T);
31 while(T--) {
32 scanf("%d", &n);
33 for(int i = 0; i < maxn; i++) vec[i].clear();
34 for(int i = 0; i < n - 1; i++) {
35 scanf("%d%d", &u, &v);
36 vec[u].pb(v), vec[v].pb(u);
37 }
38 dfs(1, -1);
39 int ans = 1;
40 for(int i = 1; i <= n; i++) {
41 if(balance[ans] > balance[i]) ans = i;
42 }
43 cout << ans << " " << balance[ans] << endl;
44 }
45 return 0;
46 }