P3478 [POI2008]STA-Station(换根法)
nofind
2019-06-06 14:37:29
题意：
给出一个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;
}
```