《鲁滨逊漂流记》题解(LCA算法求树的直径)
Description
《鲁滨逊漂流记》只讲到了鲁滨逊在岛上建立起一个自给自足的生态环境。而大家不知道的是,在此之后,鲁滨逊因为太无聊,开始探索周边的岛屿,一共 天。鲁滨逊第 天在岛 上,第 天发现了岛 ,并建立了一条到岛 的航线,(这里 为已经发现的岛,故 ),长度为 。现在鲁滨逊想知道,在第 天他的“疆土”有多大,也就是已发现的 个岛屿之间的最大距离(沿着航道走的简单路径长度)。
Input
第一行 个整数 。
接下来 行第 行 个整数 ,表示从岛 到岛 的航道。
Output
行,第 行表示第 天岛与岛之间的最大距离。
Sample
Input
6
1
2
2
1
5
Output
1
2
2
3
4
Hint
的数据,满足 ;
的数据,满足 。
Analysis
题目大意:
一棵树的构造过程为:首先以 号点为根,然后依次加入 号点。
加入 号点时,在 点中选择一个点为 ,将 号点与其相连接。
求出每次加点之后路上的最长路径长度。
算法分析:
动态求树的直径
记录下现在直径的两个端点 , ,加入一个点 时,如果可以更新直径,那么新直径一定是 或 。
可以想当然的证明,如果是 和另一点 构成 为新直径的话, 一定不会是原树直径。
所以求一下 和 $\text{dist}(s,j) $,如果大于直径就更新。
求 就用倍增求 算树上路径。
Proof
By JackJin
若树原来的直径为 在加入点 后变为 ( 为不同于 的一点)
则:
( ) 与 有交点
由于 ,标 上一点 使 为在 上的一边, ,则 (否则 为直径,而不是 ),又有 , , , ,则 ,因此 仍为直径。
( ) 与 无交点
上分别有一点 使 为一条不经过除 外的 上任意一点的简单路径,则同理有 (点C至其父节点的路径), ,则 , 不为直径。
综上,若点 加入后为直径上一点,则另一点必然为 之一。
Code
#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int N=200005;
ll ans,n,mx,x,top,depth[N],f[N][20],v[N],stack[N];
inline int lca(int x,int y)
{
if(depth[x]<depth[y])
swap(x,y);
for(register int i=18;~i;--i)
if(depth[f[x][i]]>=depth[y])
x=f[x][i];
if(x==y)
return x;
for(register int i=18;~i;--i)
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
return f[x][0];
}
int main()
{
scanf("%lld",&n);
depth[1]=1;
top=stack[1]=v[1]=1;
for(register int i=2;i<=n;++i)
{
scanf("%lld",&f[i][0]);
for(register int j=1;j<=18;++j)
f[i][j]=f[f[i][j-1]][j-1];
depth[i]=depth[f[i][0]]+1;
if(v[f[i][0]])
{
++ans;
v[i]=1;
for(;top;--top)
v[stack[top]]=0;
stack[++top]=i;
}
else
{
x=lca(stack[1],i);
ans=max(depth[i]+depth[stack[1]]-2*depth[x],ans);
if(depth[i]==depth[stack[1]])
v[stack[++top]=i]=1;
}
printf("%lld\n",ans);
}
return 0;
}
本文地址:https://blog.csdn.net/yolo_Leo/article/details/107345925
上一篇: 一个奇奇怪怪的AD问题与解决方法
下一篇: jq搜索关键字高亮显示