[dp专题]NC15033 小G有一个大树

原题链接：

https://ac.nowcoder.com/acm/problem/15033

题目大意：

树的重心模板题。

解题思路：

树形dp记录每个点下面的节点个数，求出删除一个点时的最大子树大小，比较后得到答案。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef complex <double> cp;
#define debug(a) cout<<#a<<":"<<a<<endl;
#define fr freopen("in.txt","r",stdin);
#define Fill(x,a) memset(x,a,sizeof(x))
#define cpy(a,b) memcpy(a,b,sizeof(a))
const double PI = acos(-1);
const int INF=0x3f3f3f3f;
const int N=1e6+7;
const int mod=1e9+7;
int maxn,minn;
int T,n,m,q;
struct edges{
    int u,next;
}edge[N];

int head[N];
int dp[N]; 
int cnt;
int flag;


void dfs(int u,int p){
    int v,a;
    a=0;
    dp[u]=1;
    for(int i=head[u];i!=0;i=edge[i].next){
        v=edge[i].u;
        if(v==p)    continue;
        dfs(v,u);
        dp[u]=dp[u]+dp[v];
        a=max(dp[v],a);
    }
    a=max(a,n-dp[u]);
    if(a<maxn){
        maxn=a;
        flag=u;
    }
    return ;
}

void init(){
    cnt=1;
    maxn=INF;
    Fill(head,0);
    Fill(dp,0);
    return ;
}

void add(int u,int v){
    edge[cnt].u=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}

int main(){
    int u,v;
    while(cin>>n){
        init();
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        dfs(1,0);
        cout<<flag<<" "<<maxn<<endl;
    } 

    return 0;
}