LOJ

分析

根据一个结论可以知道,距离树上一点最远的点一定是直径的两个端点之一。

于是可以用并查集维护连通块,同时维护每个连通块的直径的端点,合并两个连通块时在六条可能的直径中取个 $\max$ 即可。

需要支持加边和询问两点间距离,可以用 LCT 实现。

代码

//  ====================================
//    author: M_sea
//    website: https://m-sea-blog.com/
//  ====================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300000+10;

int n,Q;

int f[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
int fa[N],ch[N][2],rev[N],sta[N],L[N],R[N],sz[N];
void pushup(int x) { sz[x]=sz[ls(x)]+sz[rs(x)]+1; }
int nroot(int x) { return ls(fa[x])==x||rs(fa[x])==x; }
void pushdown(int x) {
    if (rev[x]) {
        if (ls(x)) rev[ls(x)]^=1,swap(ls(ls(x)),rs(ls(x)));
        if (rs(x)) rev[rs(x)]^=1,swap(ls(rs(x)),rs(rs(x)));
        rev[x]=0;
    }
}
void rotate(int x) {
    int y=fa[x],z=fa[y],k=(x==rs(y)),w=ch[x][!k];
    if (nroot(y)) ch[z][y==rs(z)]=x;
    ch[x][!k]=y,ch[y][k]=w;
    if (w) fa[w]=y; fa[y]=x,fa[x]=z;
    pushup(y);
}
void splay(int x) {
    int y=x,z=0; sta[++z]=y;
    while (nroot(y)) sta[++z]=y=fa[y];
    while (z) pushdown(sta[z--]);
    while (nroot(x)) {
        y=fa[x],z=fa[y];
        if (nroot(y)) rotate(((x==ls(y))^(y==ls(z)))?x:y);
        rotate(x);
    }
    pushup(x);
}
void access(int x) {
    for (int y=0;x;x=fa[y=x]) splay(x),rs(x)=y,pushup(x);
}
void makeroot(int x) { access(x),splay(x),rev[x]^=1,swap(ls(x),rs(x)); }
void split(int x,int y) { makeroot(x),access(y),splay(y); }
int getdis(int x,int y) { split(x,y); return sz[y]-1; }
void link(int x,int y) {
    makeroot(x); fa[x]=y;
    int tx=find(x),ty=find(y);
    int tL=L[tx],tR=R[tx],td=getdis(L[tx],R[tx]),t;
    if ((t=getdis(L[ty],R[ty]))>td) tL=L[ty],tR=R[ty],td=t;
    if ((t=getdis(L[tx],L[ty]))>td) tL=L[tx],tR=L[ty],td=t;
    if ((t=getdis(L[tx],R[ty]))>td) tL=L[tx],tR=R[ty],td=t;
    if ((t=getdis(R[tx],L[ty]))>td) tL=R[tx],tR=L[ty],td=t;
    if ((t=getdis(R[tx],R[ty]))>td) tL=R[tx],tR=R[ty],td=t;
    f[tx]=ty,L[tx]=L[ty]=tL,R[tx]=R[ty]=tR;
}

int main() {
    int type=read(); n=read(),Q=read();
    for (int i=1;i<=n;++i) L[i]=R[i]=f[i]=i,sz[i]=1;
    int lastans=0;
    while (Q--) {
        int t=read();
        if (t==1) {
            int u=read(),v=read();
            if (type) u^=lastans,v^=lastans;
            link(u,v);
        } else {
            int u=read();
            if (type) u^=lastans;
            int l=find(u),x=L[l],y=R[l];
            printf("%d\n",lastans=max(getdis(u,x),getdis(u,y)));
        }
    }
    return 0;
}
最后修改:2020 年 06 月 02 日 03 : 13 PM