1131: [POI2008]Sta

裸的treedp。。两遍dfs，第一遍求出g[i]表示以i为根的子树的深度和，第二遍求出f[i]表示以i为根的树的深度和。。

g[i]=sigma(g[k])+size[i]-1(k为i的子树),f[i]=f[fa[i]]+n-size[i]*2

size[i]表示以i为根的子树节点数，fa[i]表示i的父亲。。

#include<cstdio>
struct re{
    int u,v;
} a[2000001];
int n,sum=0;
long long f[1000001],g[1000001],size[1000001],fa[1000001];
int head[1000001],next[2000001];
void dfs(int i){
    size[i]=1;
    g[i]=0;
    for (int j=head[i];j;j=next[j]){
        int k=a[j].v;
        if (k!=fa[i]){
            fa[k]=i;
            dfs(k);
            size[i]+=size[k];
            g[i]+=g[k];
        }
    }
    g[i]+=size[i]-1;
}
void dfs2(int i){
    if (i!=1){
        int j=fa[i];
        f[i]=f[j]-size[i]+n-size[i];
        //printf("f[%d]=%d\n",i,f[i]);
    }
    for (int j=head[i];j;j=next[j]){
        int k=a[j].v;
        if (fa[i]!=k) dfs2(k);
    }
}
void build(int u,int v){
    a[++sum].u=u;
    a[sum].v=v;
    next[sum]=head[u];
    head[u]=sum;
}
int main(){
    scanf("%d",&n);
    int u,v;
    for (int i=1;i<=n-1;i++){
        scanf("%d%d",&u,&v);
        build(u,v);
        build(v,u);
    }
    dfs(1);
    f[1]=g[1];
    dfs2(1);
    int j=0;
    for (int i=1;i<=n;i++){
        //printf("g[%d]=%d\n",i,g[i]);
        if (f[i]>f[j]) j=i;
    }
    printf("%d\n",j);
}