当前位置： 移动技术网 > 互联网>游戏 > 荐 《鲁滨逊漂流记》题解(LCA算法求树的直径)

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

2020年07月15日  | 移动技术网互联网  | 我要评论

Description

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

Input

第一行 11 个整数 NN 。

接下来 N−1N-1 行第 ii 行 11 个整数 XiX_i ，表示从岛 ii 到岛 XiX_i 的航道。

Output

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

Sample

Input

6
1
2
2
1
5

Output

1
2
2
3
4

Hint

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

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

Analysis

题目大意：

一棵树的构造过程为：首先以 11 号点为根，然后依次加入 2∼n2 \sim n 号点。
加入 ii 号点时，在 1∼(i−1)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

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

则：

( 11 ) CSCS 与 ABAB 有交点 DD

由于 CS>ABCS>AB ，标 CSCS 上一点 EE 使 CECE 为在 CSCS 上的一边， CE=1CE=1 ，则 SE=ABSE=AB （否则 SESE 为直径，而不是 ABAB ），又有 AB≥AEAB \geq AE ， AB≥BSAB \geq BS ， SE≥ASSE \geq AS ， SE≥BSSE \geq BS ，则 AD=BD=DE=DSAD=BD=DE=DS ，因此 AC(A−D−E−C)AC(A-D-E-C) 仍为直径。

( 22 ) CSCS 与 ABAB 无交点

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

综上，若点 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

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网