欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  互联网

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

程序员文章站 2022-04-12 08:10:48
Description《鲁滨逊漂流记》只讲到了鲁滨逊在岛上建立起一个自给自足的生态环境。而大家不知道的是,在此之后,鲁滨逊因为太无聊,开始探索周边的岛屿,一共 NNN 天。鲁滨逊第 111 天在岛 111 上,第 iii 天发现了岛 iii ,并建立了一条到岛 XiX_iXi​ 的航线,(这里 XiX_iXi​ 为已经发现的岛,故 Xi

Description

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

Input

第一行 11 个整数 NN

接下来 N1N-1 行第 ii11 个整数 XiX_i ,表示从岛 ii 到岛 XiX_i 的航道。

Output

N1N-1 行,第 ii 行表示第 i+1i+1 天岛与岛之间的最大距离。

Sample

Input

6
1
2
2
1
5

Output

1
2
2
3
4

Hint

30%30\% 的数据,满足 N103N \leq 10^3

100%100\% 的数据,满足 2N2×1052 \leq N \leq 2 \times 10^5

Analysis

题目大意:

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

算法分析:

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

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

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

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

Proof

By JackJin

若树原来的直径为 ABAB 在加入点 CC 后变为 CSCSSS 为不同于 A,BA,B 的一点)

则:

( 11 ) CSCSABAB 有交点 DD

由于 CS>ABCS>AB ,标 CSCS 上一点 EE 使 CECE 为在 CSCS 上的一边, CE=1CE=1 ,则 SE=ABSE=AB (否则 SESE 为直径,而不是 ABAB ),又有 ABAEAB \geq AEABBSAB \geq BSSEASSE \geq ASSEBSSE \geq BS ,则 AD=BD=DE=DSAD=BD=DE=DS ,因此 AC(ADEC)AC(A-D-E-C) 仍为直径。

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

( 22 ) CSCSABAB 无交点

CS,ABCS,AB 上分别有一点 D,ED,E 使 DEDE 为一条不经过除 D,ED,E 外的 CS,ABCS,AB 上任意一点的简单路径,则同理有 AE>CD1AE>CD-1 (点C至其父节点的路径), BE>DSBE>DS ,则 AB>CSAB>CSCSCS 不为直径。

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

综上,若点 CC 加入后为直径上一点,则另一点必然为 A,BA,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