BZOJ 4668 冷战

注意到一个性质，如果加入的边 $<u,v>$ 已经在连通块里面，发现连通块任意两点都是联通的，于是加入边并不会对答案有任何影响，我们就不加入这一条边。

于是发现这张图在任意时刻都是一个森林，森林就比较好办，考虑记录加入边的时间 $tim[]$ ，于是答案即是 $\max\{ tim[w] ,w \in route(u,v)\}$ ， $route(u,v)$ 表示 $u,v$ 之间的路径，于是从 $u,v$ 两点分别往上跳并且记录最大值，跳到 $lca$ 为止。

考虑到这样会超时，不妨考虑启发式合并，于是每次查询均摊 $\log (n)$ ，可以AC。

注意异或不要少了。

#include <bits/stdc++.h>
#define MAXN 500005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
namespace BCJ{
    static int fa[MAXN],sz[MAXN],dep[MAXN],tim[MAXN];
    inline void Init(int n){
        for (int i=1;i<=n;++i) fa[i]=i,sz[i]=1;
    }
    int Find(int i){
        return fa[i]==i?i:Find(fa[i]);
    }
    int InitDep(int i){
        return (fa[i]==i)?(dep[i]):(dep[i]=(InitDep(fa[i])+1));
    }
    inline void Merge(int t,int u,int v){
        u=Find(u),v=Find(v);
        if (u==v) return ;
        if (sz[u]<sz[v]) swap(u,v);//v -> u
        sz[u]+=sz[v];
        fa[v]=u;
        tim[v]=t;//连边时间
    }
    inline int Query(int u,int v){
        if (InitDep(u)<=InitDep(v)) swap(u,v);
        int ans=0;
        while (dep[u]>dep[v]) ans=max(ans,tim[u]),u=fa[u];
        if (u==v) return ans;
        while (u!=v) ans=max(ans,max(tim[u],tim[v])),u=fa[u],v=fa[v];
        return ans;
    }
}
using namespace BCJ;
int main(){
    int n=read(),m=read();
    Init(n);
    int lstans=0,cnt=0;
    while (m--){
        int opr=read(),u=read()^lstans,v=read()^lstans;
        if (opr==0) {
            Merge(++cnt,u,v);
        }
        else {
            if (Find(u)!=Find(v)) printf("%d\n",lstans=0);
            else printf("%d\n",lstans=Query(u,v));
        }
    }
}