《鲁滨逊漂流记》题解(LCA算法求树的直径)

Description

《鲁滨逊漂流记》只讲到了鲁滨逊在岛上建立起一个自给自足的生态环境。而大家不知道的是，在此之后，鲁滨逊因为太无聊，开始探索周边的岛屿，一共 $N$ 天。鲁滨逊第 $1$ 天在岛 $1$ 上，第 $i$ 天发现了岛 $i$ ，并建立了一条到岛 $X_i$ 的航线，（这里 $X_i$ 为已经发现的岛，故 $X_i<i$ ），长度为 $1$ 。现在鲁滨逊想知道，在第 $i$ 天他的“疆土”有多大，也就是已发现的 $2$ 个岛屿之间的最大距离（沿着航道走的简单路径长度）。

Input

第一行 $1$ 个整数 $N$ 。

接下来 $N-1$ 行第 $i$ 行 $1$ 个整数 $X_i$ ，表示从岛 $i$ 到岛 $X_i$ 的航道。

Output

$N-1$ 行，第 $i$ 行表示第 $i+1$ 天岛与岛之间的最大距离。

Sample

Input

6
1
2
2
1
5

Output

1
2
2
3
4

Hint

$30\%$ 的数据，满足 $N \leq 10^3$ ；

$100\%$ 的数据，满足 $2 \leq N \leq 2 \times 10^5$ 。

Analysis

题目大意：

一棵树的构造过程为：首先以 $1$ 号点为根，然后依次加入 $2 \sim n$ 号点。
加入 $i$ 号点时，在 $1 \sim (i-1)$ 点中选择一个点为 $f_i$ ，将 $i$ 号点与其相连接。
求出每次加点之后路上的最长路径长度。

算法分析：

动态求树的直径
记录下现在直径的两个端点 $i$ , $j$ ,加入一个点 $s$ 时,如果可以更新直径,那么新直径一定是 $(s,j)$ 或 $(s,i)$ 。

可以想当然的证明,如果是 $s$ 和另一点 $t$ 构成 $(s,t)$ 为新直径的话, $(i,j)$ 一定不会是原树直径。

所以求一下 $\text{dist}(s,i)$ 和 $\text{dist}(s,j) $,如果大于直径就更新。

求 $\text{dist}$ 就用倍增求 $\text{LCA}$ 算树上路径。

Proof

By JackJin

若树原来的直径为 $AB$ 在加入点 $C$ 后变为 $CS$（ $S$ 为不同于 $A,B$ 的一点）

则：

( $1$ ) $CS$ 与 $AB$ 有交点 $D$

由于 $CS>AB$ ，标 $CS$ 上一点 $E$ 使 $CE$ 为在 $CS$ 上的一边， $CE=1$ ，则 $SE=AB$ （否则 $SE$ 为直径，而不是 $AB$ ），又有 $AB \geq AE$ ， $AB \geq BS$ ， $SE \geq AS$ ， $SE \geq BS$ ，则 $AD=BD=DE=DS$ ，因此 $AC(A-D-E-C)$ 仍为直径。

( $2$ ) $CS$ 与 $AB$ 无交点

$CS,AB$ 上分别有一点 $D,E$ 使 $DE$ 为一条不经过除 $D,E$ 外的 $CS,AB$ 上任意一点的简单路径，则同理有 $AE>CD-1$ （点C至其父节点的路径）， $BE>DS$ ，则 $AB>CS$ ， $CS$ 不为直径。

综上，若点 $C$ 加入后为直径上一点，则另一点必然为 $A,B$ 之一。

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