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

Description

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

Input

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

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

Output

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

Sample

Input

Output

Hint

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

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

Analysis

题目大意：

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

算法分析：

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

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

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

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

Proof

By JackJin

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

则：

( 1 1 1 ) C S CS CS 与 A B AB AB 有交点 D D D

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

( 2 2 2 ) C S CS CS 与 A B AB AB 无交点

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

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

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

Description

Input

Output

Sample

Hint

Analysis

Proof

Code

相关推荐