扔到一个块里是并查集的工作
然后怎样维护最大的时间？
采用不路径压缩的并查集按秩合并保证复杂度，边权为时间，询问时暴力往上跳
一开始以为连接两个联通块要y向x连边并且y的祖先反向连，实际上是不用的，因为隶属于同个联通块要去其他联通块这是必须边
是不是就有动态维护最小生成树的味道了
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int fa[510000],dep[510000],tim[510000]; int findfa(int x) { if(fa[x]<0)return x; int f=findfa(fa[x]);dep[x]=dep[fa[x]]+1; return f; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int n,Q,lastans=0; scanf("%d%d",&n,&Q); for(int i=1;i<=n;i++)fa[i]=-1,dep[i]=1,tim[i]=0; int T_T=0,s=0; while(Q--) { int op,x,y; scanf("%d%d%d",&op,&x,&y); x^=lastans,y^=lastans; if(op==0) { T_T++; int fx=findfa(x),fy=findfa(y); if(fx!=fy) { if(fa[fx]>fa[fy])swap(x,y),swap(fx,fy); fa[fx]=fa[fx]+fa[fy]; tim[fy]=T_T;fa[fy]=fx; } } else { s++; if(s==204) { int zz;zz++; } int fx=findfa(x),fy=findfa(y); if(fx!=fy)lastans=0; else { if(dep[x]>dep[y])swap(x,y); int mmax=0; while(dep[x]<dep[y])mmax=max(mmax,tim[y]),y=fa[y]; while(x!=y)mmax=max(mmax,max(tim[x],tim[y])),x=fa[x],y=fa[y]; lastans=mmax; } printf("%d ",lastans); } } return 0; }