【Foreign】远行 [LCT]

远行

Time Limit: 20 Sec Memory Limit: 256 MB

Description

Input

Output

Sample Input

　　0
　　5 10
　　1 4 5
　　2 3
　　2 5
　　2 1
　　1 5 3
　　1 1 4
　　2 3
　　2 5
　　1 5 2
　　2 1

Sample Output

　　0
　　1
　　0
　　3
　　2
　　3

HINT

Main idea

　　每次连上一条边，询问一个点和其能到达最远的点的距离。

Solution

　　由于每次要脸上一条边，我们显然使用LCT，然后一个点到达的最远的点必然是树的直径上的端点，我们合并两棵树维护直径的时候，暴力分几种情况讨论一下即可。

Code

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<vector>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int MOD = 1e9+;

 int Type,n,Q;

 int opt,x,y;

 int fat[ONE];

 int Ans;

 int get()

 {

         int res=,Q=;    char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 int Find(int x)

 {

         if(fat[x]==x) return x;

         return fat[x]=Find(fat[x]);

 }

 namespace LCT

 {

         int lc[ONE],rc[ONE],fa[ONE];

         int hasRev[ONE];

         int L[ONE],R[ONE],dis[ONE],size[ONE];

         void pre()

         {

             for(int i=;i<=n;i++)

                 fat[i]=L[i]=R[i]=i,

                 size[i]=;

         }

         void Update(int x)

         {

             size[x] = size[lc[x]] + size[rc[x]] + ;

         }

         bool is_real(int x)

         {

             return (lc[fa[x]]==x || rc[fa[x]]==x);

         }

         void tag_rev(int x)

         {

             hasRev[x]^=;

             swap(lc[x],rc[x]);

         }

         void tag_down(int x)

         {

             if(hasRev[x])

             {

                 tag_rev(lc[x]);

                 tag_rev(rc[x]);

                 hasRev[x]=;

             }

         }

         void Turn(int x)

         {

             int y=fa[x],z=fa[y];

             int b= x==lc[y]?rc[x]:lc[x];

             fa[y]=x;    fa[x]=z;

             if(b) fa[b]=y;

             if(z)

             {

                 if(y==lc[z]) lc[z]=x;

                 else if(y==rc[z]) rc[z]=x;

             }

             if(x==lc[y]) rc[x]=y,lc[y]=b;

             else lc[x]=y,rc[y]=b;

             Update(y);    Update(x);

         }

         void Splay(int x)

         {

             static int anc[ONE];

             int anc_num=;

             anc[++anc_num] = x;

             for(int i=x; is_real(i); i=fa[i]) anc[++anc_num]=fa[i];

             while(anc_num>) tag_down(anc[anc_num--]);

             while(is_real(x))

             {

                 if(is_real(fa[x]))

                 {

                     if( (lc[fa[x]]==x) == (lc[fa[fa[x]]]==fa[x]) ) Turn(fa[x]);

                     else Turn(x);

                 }

                 Turn(x);

             }

         }

         void access(int x)

         {

             for(int p=x,q=; p; q=p,p=fa[q])

             {

                 Splay(p);

                 rc[p] = q;

                 Update(p);

             }

         }

         void make_root(int x)

         {

             access(x);    Splay(x);    tag_rev(x);

         }

         int dist(int x,int y)

         {

             make_root(x);    access(y);    Splay(y);    return size[y]-;

         }

         void link(int x,int y)

         {

             int lx,rx,ly,ry;

             int Fx=Find(x), Fy=Find(y);

             fat[Fy] = Fx;

             make_root(x);    fa[x]=y;

             lx = L[Fx];    rx = R[Fx];    ly = L[Fy];    ry = R[Fy];

             if(dist(lx,rx) >= dis[Fx]) dis[Fx]=dist(lx,rx), L[Fx]=lx, R[Fx]=rx;

             if(dist(ly,ry) >= dis[Fx]) dis[Fx]=dist(ly,ry), L[Fx]=ly, R[Fx]=ry;

             if(dist(lx,ly) >= dis[Fx]) dis[Fx]=dist(lx,ly), L[Fx]=lx, R[Fx]=ly;

             if(dist(lx,ry) >= dis[Fx]) dis[Fx]=dist(lx,ry), L[Fx]=lx, R[Fx]=ry;

             if(dist(rx,ly) >= dis[Fx]) dis[Fx]=dist(rx,ly), L[Fx]=rx, R[Fx]=ly;

             if(dist(rx,ry) >= dis[Fx]) dis[Fx]=dist(rx,ry), L[Fx]=rx, R[Fx]=ry;

         }

         void Query(int x)

         {

             int Fx=Find(x);

             Ans = max( dist(L[Fx],x),dist(R[Fx],x) );

             printf("%d\n",Ans);

         }

 }

 int main()

 {

         Type=get();

         n=get();    Q=get();

         LCT::pre();

         while(Q--)

         {

             opt = get();

             if(opt == )

             {

                 x=get();    y=get();

                 if(Type==) x^=Ans, y^=Ans;

                 LCT::link(x,y);

             }

             else

             {

                 x=get();

                 if(Type==) x^=Ans;

                 LCT::Query(x);

             }

         }

 }

巴特西