P3478 [POI2008]STA-Station(换根法)

· · 题解

题意：

给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大。

解析：

首先暴力的做法就是对于每个点都用dfs求一遍,之后比较大小。

但是我们发现实际上对于x我们可以用它的父亲节点推出它的答案。

如图：

以5为根时：

以4为根时： 观察发现:4的子树(包括自己)深度都减少了1,原根5的子树的深度都增加了1。

也就是说:对于x,它的父亲是y。

f[x]=f[y]-size[x]+n-size[x].

也就是说只要求出一个点,我们就可以用它求出其他点的ans。

这个方法叫二次扫描与换根法。

注:记得开long long

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
struct edge
{
    int to,nxt;
}e[maxn<<1];
int n,cnt,id;
int head[maxn];
long long ans;
long long f[maxn],dep[maxn],size[maxn];
inline void add(int u,int v)
{
    e[++cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].to=v;
}
void dfs1(int x,int fa)
{
    size[x]=1;dep[x]=dep[fa]+1;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==fa) continue;
        dfs1(y,x);
        size[x]+=size[y];
    }
}
void dfs2(int x,int fa)
{
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==fa) continue;
        f[y]=f[x]+n-2*size[y];
        dfs2(y,x);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs1(1,0);
    for(int i=1;i<=n;i++) f[1]+=dep[i];
    dfs2(1,0);
    for(int i=1;i<=n;i++) if(ans<f[i]) ans=f[i],id=i;
    printf("%d",id);
    return 0;
}