题解 P3478 【[POI2008]STA-Station】

· · 题解

换根dp

设 f[i] 为 i 为根，所有结点的深度之和。

考虑先求一遍 f[rt]，rt 初始值为 1，表示 一开始的根。

并且令 rt=1 时，以 i 为根的子树大小为 siz[i]

比如说对于树上两点 u=4,v=2，rt=1 时 fa[u]=v，那么此时假设已经求出 f[v] 考虑如何推出 f[u]

左边数字为深度。

观察红色部分，可以发现 rt 由 v->u时，每个节点深度 -1，总答案就是减 siz[4]=siz[u]

观察蓝色部分，可以发现 rt 由 v->u时，每个节点深度 +1，总答案也就是 siz[1]-siz[2]=n-siz[u]

所以当 rt 由 v->u 时，f[v]=f[u]+siz[u]+n-siz[u]=f[y]+n-siz[u]

方程就搞出来了。

code 
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long 
inline int read(){
    register int x=0,f=0,ch=getchar();
    while('0'>ch||ch>'9')f^=ch=='-',ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
    return f?-x:x;
}
const int MAX=1000005;
int n,u,v;
struct E{
    int e,next;
}e[MAX<<1];
int head[MAX],cnt=1,f[MAX],ans=-1;
inline void add(int u,int v){
    e[cnt]=(E){v,head[u]};head[u]=cnt++; 
}
int siz[MAX],dep[MAX];
void dfs(int x,int fa){
    siz[x]=1;dep[x]=dep[fa]+1;
    f[1]+=dep[x];
    for(register int i=head[x];i;i=e[i].next){
        if(e[i].e!=fa){
            dfs(e[i].e,x);
            siz[x]+=siz[e[i].e];
        }
    }
}
void dfs1(int x,int fa){
    for(register int i=head[x];i;i=e[i].next){
        if(e[i].e!=fa){
            f[e[i].e]=f[x]+n-2*siz[e[i].e];
            dfs1(e[i].e,x); 
        }
    }
}
signed main(){
    n=read();
    for(register int i=1;i<n;++i){
        u=read(),v=read();
        add(u,v);add(v,u);
    }
    dep[0]=-1;
    dfs(1,0);
    dfs1(1,0);
    for(register int i=1;i<=n;++i){
        if(f[ans]<f[i])ans=i;
    }
    printf("%d\n",ans);
    return 0;
}