題意簡(jiǎn)要說(shuō)明下，給出一顆樹(shù)，如果刪除一個(gè)節(jié)點(diǎn)，則會(huì)將這棵樹(shù)變成一棵子樹(shù)或者森林。定義節(jié)點(diǎn)的平衡數(shù)為刪除這個(gè)節(jié)點(diǎn)后子樹(shù)的最大節(jié)點(diǎn)數(shù)。求最小平衡數(shù)的節(jié)點(diǎn)以及最小平衡數(shù)。
還是老方法，樹(shù)形DP，子樹(shù)的節(jié)點(diǎn)數(shù)顯然就為size[son[pos]]，以及total-size[pos]，取其最大值和當(dāng)前答案比較即可。
貼代碼
1 # include <cstdio>
2 # include <cstring>
3 using namespace std;
4 int g[20005],size[20005];
5 int v[50000],nxt[50000],c;
6 int num,total,ans=0xfffffff,minnum;
7 inline void insert(int a,int b)
8 {
9 v[c]=b;
10 nxt[c]=g[a];
11 g[a]=c++;
12 }
13 void dfs(int pos,int fa)
14 {
15
16 size[pos]=1;
17 for(int p=g[pos];p!=-1;p=nxt[p])
18 {
19 if(v[p]!=fa)
20 {
21 dfs(v[p],pos);
22 size[pos]+=size[v[p]];
23 }
24 }
25
26 }
27 void cal(int pos,int fa)
28 {
29 int maxnum=-1;
30 for(int p=g[pos];p!=-1;p=nxt[p])
31 if(v[p]!=fa)
32 {
33 cal(v[p],pos);
34 if(size[v[p]]>maxnum)
35 maxnum=size[v[p]];
36 }
37 if(pos!=1&&total-size[pos]>maxnum)
38 maxnum=total-size[pos];
39 if(maxnum<ans||maxnum==ans&&pos<minnum)
40 ans=maxnum,minnum=pos;
41
42 }
43 int main()
44 {
45 int t;
46 scanf("%d",&t);
47 while(t--)
48 {
49 c=0;
50 memset(g,-1,sizeof(g));
51 scanf("%d",&num);
52 for(int i=1;i<num;i++)
53 {
54 int a,b;
55 scanf("%d%d",&a,&b);
56 insert(a,b);
57 insert(b,a);
58 }
59 dfs(1,-1);
60 ans=0xfffffff;
61 total=size[1];
62 cal(1,-1);
63 printf("%d %d\n",minnum,ans);
64 }
65 return 0;
66
67 }