思路:考试的时候打了LCT，自以为能过，没想到只能过80..

考完一想:lct的做法点数是100W,就算是nlogn也会T。

讲一下lct的做法把:首先如果一条边连接的两个点都在同一个联通块内，那么这条边对答案没有影响，可以忽略，因此，问题变成了每次询问两个点中路径上权值最大的边(这里的权值我们令它为加入这条边的时间)，边我们用一个点连接两个端点来表示。

正解:由于是无根树，因此我们用并查集按秩合并，每次把小的加到大的里面去，询问的时候暴力走lct查找最大即可。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 int fa[500005],n,m,size[500005],ty[500005],vis[500005],vistag; 7 int read(){ 8     int t=0,f=1;char ch=getchar(); 9     while (ch<'0'||ch>'9'){
   if (ch=='-')f=-1;ch=getchar();}10     while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}11     return t*f;12 }13 int find(int x){14     if (fa[x]==x) return x;15     else return fa[x]=find(fa[x]);16 }17 int main(){18     n=read();m=read();19     for (int i=1;i<=n;i++) fa[i]=size[i]=1,ty[i]=0;20     int Case=0,lastans=0;21     for (int i=1;i<=m;i++){22         int opt=read(),u=read()^lastans,v=read()^lastans;23         if (!opt){24             ++Case;25             u=find(u),v=find(v);26             if (u!=v){27                 if (size[u]>size[v]) std::swap(u,v);28                 fa[u]=v;29                 size[v]+=size[u];30                 ty[u]=Case;31             }else{32                 ++vistag;33                 int fu=u,fv=v;34                 for (;;u=fa[u]){35                     vis[u]=vistag;36                     if (fa[u]==u) break;37                 }38                 int lca=0;39                 for (;;v=fa[v]){40                     if (vis[v]==vistag&&!lca) lca=v;41                     if (fa[v]==v) break;42                 }43                 if (u!=v){44                     printf("%d\n",lastans=0);45                     continue;46                 }else{47                     int ans=0;48                     for (;fu!=lca;fu=fa[fu]) ans=std::max(ans,ty[fu]);49                     for (;fv!=lca;fv=fa[fv]) ans=std::max(ans,ty[fv]);50                     printf("%d\n",lastans=ans);51                 }52             }53         }54     }55 }