树形dp&&树的重心（D

题目链接：https://cn.vjudge.net/contest/277955#problem/D

题目大意：求树的重心（树的重心指的是树上的某一个点，删掉之后形成的多棵树中节点数最大值最小）。

具体思路：对于每一个点，我们求出以当前的点为根的根数的节点个数，然后在求树的重心的时候，一共有两种情况，一种树去除该点后这个点的子节点中存在所求的最大值，还有一种情况是这个点往上会求出最大值，往上的最大值就是（n-dp[rt][0]）.

AC代码：

 1 #include<iostream>
 2 #include<cmath>
 3 #include<stack>
 4 #include<stdio.h>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<vector>
 8 #include<cstring>
 9 using namespace std;
10 # define inf 0x3f3f3f3f
11 # define ll long long
12 const int maxn = 2e5+100;
13 struct node
14 {
15     int nex;
16     int to;
17 } edge[maxn];
18 int num,head[maxn],dp[maxn][3],father[maxn];
19 int sto[maxn],minn,n;
20 void init()
21 {
22     minn=inf;
23     num=0;
24     memset(head,-1,sizeof(head));
25     memset(dp,0,sizeof(dp));
26 }
27 void addedge(int fr,int to)
28 {
29     edge[num].to=to;
30     edge[num].nex=head[fr];
31     head[fr]=num++;
32 }
33 void dfs1(int fr,int rt)
34 {
35     dp[fr][0]=1;
36     for(int i=head[fr]; i!=-1; i=edge[i].nex)
37     {
38         int to=edge[i].to;
39         if(to==rt)
40             continue;
41         dfs1(to,fr);
42         dp[fr][0]+=dp[to][0];
43     }
44 }
45 void dfs2(int fr,int rt)
46 {
47     dp[fr][1]=n-dp[fr][0];
48     for(int i=head[fr]; i!=-1; i=edge[i].nex)
49     {
50         int to=edge[i].to;
51         if(to==rt)
52             continue;
53         dfs2(to,fr);
54         dp[fr][1]=max(dp[fr][1],dp[to][0]);
55     }
56     minn=min(minn,dp[fr][1]);
57 }
58 int main()
59 {
60     init();
61     scanf("%d",&n);
62     int t1,t2;
63     for(int i=2; i<=n; i++)
64     {
65         scanf("%d %d",&t1,&t2);
66         addedge(t1,t2);
67         addedge(t2,t1);
68     }
69     dfs1(1,-1);
70     dfs2(1,-1);
71     int flag=1;
72     for(int i=1; i<=n; i++)
73     {
74         if(dp[i][1]==minn)
75         {
76             if(flag)
77             {
78                 printf("%d",i);
79                 flag=0;
80             }
81             else
82                 printf(" %d",i);
83         }
84     }
85     printf("
");
86     return 0;
87 }
88 
89