树形DP

2018-07-13 15:11:31


#include<bits/stdc++.h>
using namespace std;
struct edge{
    int v,next;
}a[100001];
int head[100001];
int siz[50001];
int cnt,ans,maxblock=-1,root,n;
void add(int x,int v) 
{
    cnt++;
    a[cnt].next=head[x];
    a[cnt].v=v;
    head[x]=cnt;
} 
void dfs1(int x)
{
    int block=0;
    siz[x]=1;
    for(int i=head[x];i;i=a[i].next)
    {
        int v=a[i].v;
        if(!siz[v])
        {
            dfs1(v);
            siz[x]+=siz[v];
            block=max(block,siz[v]);
        }
    }
    block=max(block,n-siz[x]);
    if(block==maxblock)root=min(root,x);
    if(block<maxblock||maxblock==-1)
    {
        maxblock=block;root=x;
    }
}
void dfs(int x)
{
    siz[x]=1;
    for(int i=head[x];i;i=a[i].next)
    {
        int v=a[i].v;
        if(!siz[v])
        {
            dfs(v);
            siz[x]+=siz[v];
        }
    }
    ans+=(siz[x]-1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);add(x,y);add(y,x);
    }
    dfs1(1);
    memset(siz,0,sizeof(siz));
    dfs(root);
    printf("%d %d",root,ans);
}