10min80分
20min100分
调的很快
算法要素:树形dp
换根dp可以处理的问题:
求出一棵树以每一个点为根节点之后,树的最大深度和
算法流程:
(1)以1或其他任意一个节点为根,dfs遍历一次处理出dep
(2)再dfs一次处理dep
关于一些细节错误:
我最开始考虑要统计根节点向下移的深度,但是这样其实是错误的,因为根节点下移之后会出现下移深度为1和下移深度为3时某些节点的深度不变。
至于为什么,想象一下下移一定深度之后整条路径上下反转了一次,因此深度不变。
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+50;
int n,head[maxn],ecnt=-1;
long long dep[maxn],sz[maxn];
int id=0;
long long ans=0,sum=0;
long long f[maxn];
struct mint
{
int nxt,v,u;
}e[maxn<<1];
inline void addline(int u,int v)
{
e[++ecnt].nxt=head[u];
e[ecnt].v=v;
e[ecnt].u=u;
head[u]=ecnt;
}
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1;
sz[x]=1;
for(int i=head[x];~i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa) continue;
dfs(v,x);
sz[x]+=sz[v];
}
}
void getans(int x,int fa)
{
for(int i=head[x];~i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa) continue;
f[v]=f[x]+(n-sz[v])-sz[v];
getans(v,x);
}
}
int main()
{
scanf("%d",&n);
memset(head,-1,sizeof(head));
for(int i=1;i<=n-1;++i)
{
int x,y;
scanf("%d%d",&x,&y);
addline(x,y);
addline(y,x);
}
dep[0]=-1;
dfs(1,0);
for(int i=1;i<=n;++i) f[1]+=dep[i];
getans(1,0);
for(int i=1;i<=n;++i)
{
if(f[i]>ans)
{
ans=f[i];
id=i;
}
}
printf("%d\n",id);
return 0;
}