「题解」「USACO18FEB」New Barns P

题目链接:USACO18FEB/Luogu P4271/BZOJ 5192

题解

思路

这题在不断往已有的节点上加边连点,形成了森林。

先看操作二:

  • Q k 表示查询在 $ k $ 节点所在的连通块中,距它最远的点的距离。这里距离的定义是两点间经过的边数。

显然,设树的直径的左右端点为 $ l, r $,答案为 $ \max (\text{dis}(k, l), \text{dis}(k, r) ) $。

那么我们分析操作一,发现我们只需要简单的合并即可。

代码

渐进时间复杂度为 $ \Theta ( q \log _ {2} q ) $。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=100000+5; // 数据范围
const int MAXLOG2N=17+1; // log _ 2 (100000) = 16.609640474436811739351597147447

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int q;

inline void Read(void){
    q=read();
    return;
}

struct TreeD{
    int l,r; // 储存树的直径的左右端点
    inline TreeD(reg int l=0,reg int r=0):l(l),r(r){
        return;
    }
};

int n;
int dep[MAXN]; // 节点深度
int color[MAXN]; // 每颗树的代表节点的编号
int fa[MAXN][MAXLOG2N]; // 倍增求 LCA 用数组
TreeD a[MAXN]; // 储存树的直径的左右端点

inline int LCA(int x,int y){ // 倍增求 LCA 模板
    if(dep[x]>dep[y])
        swap(x,y);
    for(reg int i=MAXLOG2N-1;i>=0;--i)
        if(dep[fa[y][i]]>=dep[x])
            y=fa[y][i];
    if(x==y)
        return x;
    for(reg int i=MAXLOG2N-1;i>=0;--i)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}

inline int GetDis(reg int x,reg int y){
    reg int lca=LCA(x,y);
    return dep[x]+dep[y]-(dep[lca]<<1); // 求距离
}

inline void Work(void){
    while(q--){
        static char opt;
        do
            opt=getchar();
        while(opt!='B'&&opt!='Q'); // 读入操作编号
        if(opt=='B'){
            static int p;
            p=read();
            ++n; // 新增节点
            if(p==-1){
                fa[n][0]=0;
                dep[n]=0;
                color[n]=n;
                a[n]=TreeD(n,n);
            }
            else{
                fa[n][0]=p;
                dep[n]=dep[p]+1;
                color[n]=color[p];
                for(reg int i=1;i<MAXLOG2N;++i)
                    fa[n][i]=fa[fa[n][i-1]][i-1];
                reg int temp=color[p];
                reg int dis1=GetDis(n,a[temp].l);
                reg int dis3=GetDis(a[temp].l,a[temp].r);
                if(dis1>dis3)
                    a[temp].r=n; // 更新右端点
                reg int dis2=GetDis(n,a[temp].r);
                if(dis2>dis3)
                    a[temp].l=n; // 更新左端点
            }
        }
        else if(opt=='Q'){
            static int k;
            k=read();
            reg int temp=color[k];
            int dis1=GetDis(a[temp].l,k);
            int dis2=GetDis(a[temp].r,k);
            printf("%d\n",max(dis1,dis2)); // 求最大距离
        }
    }
    return;
}