uoj207共价大爷游长沙

话说我可能还没有调出魔法森林呢。。。说好的lct第一题呢。。。

又是一个随机化的方法，毕竟又是判定性的问题

这次是判断一些路径是否经过一条定边

若把路径上的边全部异或上一个路径的权值

只要判断这条边的权值是否是所有路径的权值异或和就没了

lct维护链上异或和就好了

 #include<bits/stdc++.h>

 #define MAXN 100010

 #define MAXM 300010

 #define ll long long

 using namespace std;

 int fa[MAXN],son[MAXN][],siz[MAXN],pe[MAXN],ne[MAXN],fe[MAXN],le[MAXN],sum[MAXN],ch[MAXN];

 int val[MAXN+MAXM];

 bool rev[MAXN];

 int st[MAXN],tp;

 int v[MAXM],v1[MAXM],v2[MAXM],cnt;

 int n,m;

 int S;

 int tot;

 int rd()

 {

     if(RAND_MAX==) return (rand()<<)+rand();

     else return rand();

 }

 bool ir(int x)

 {

     return son[fa[x]][]!=x&&son[fa[x]][]!=x;

 }

 void ud(int x)

 {

     siz[x]=siz[son[x][]]+siz[son[x][]]+;

     sum[x]=;

     fe[x]=pe[x];

     le[x]=ne[x];

     if(son[x][])

     {

         sum[x]^=sum[son[x][]]^val[pe[x]];

         fe[x]=fe[son[x][]];

     }

     if(son[x][])

     {

         sum[x]^=sum[son[x][]]^val[ne[x]];

         le[x]=le[son[x][]];

     }

 }

 void torev(int x)

 {

     if(!x)

         return;

     swap(son[x][],son[x][]);

     swap(pe[x],ne[x]);

     swap(fe[x],le[x]);

     rev[x]^=;

 }

 void toch(int x,int y)

 {

     if(!x)

         return;

     if(siz[x]&^)

         sum[x]^=y;

     if(son[x][])

         val[pe[x]]^=y;

     if(son[x][])

         val[ne[x]]^=y;

     ch[x]^=y;

 }

 void pd(int x)

 {

     if(rev[x])

     {

         torev(son[x][]);

         torev(son[x][]);

         rev[x]=;

     }

     if(ch[x])

     {

         toch(son[x][],ch[x]);

         toch(son[x][],ch[x]);

         ch[x]=;

     }

 }

 void cot(int x,int y,int z)

 {

     if(x)

         fa[x]=y;

     if(y)

         son[y][z]=x;

 }

 void rot(int x,bool z)

 {

     int xx=fa[x],xxx=fa[xx];

     cot(son[x][z],xx,z^);

     if(ir(xx))

         fa[x]=xxx;

     else

         cot(x,xxx,son[xxx][]==xx);

     cot(xx,x,z);

     ud(xx);

 }

 void apd(int x)

 {

     int i;

     st[++tp]=x;

     for(i=x;!ir(i);i=fa[i])

         st[++tp]=fa[i];

     for(;tp;tp--)

         pd(st[tp]);

 }

 void splay(int x)

 {

     apd(x);

     while(!ir(x))

     {

         int xx=fa[x],xxx=fa[xx];

         if(ir(xx))

             rot(x,son[xx][]==x);

         else

         {

             bool z=son[xxx][]==xx;

             if(son[xx][z]==x)

             {

                 rot(x,z^);

                 rot(x,z);

             }

             else

             {

                 rot(xx,z);

                 rot(x,z);

             }

         }

     }

     ud(x);

 }

 void acs(int x)

 {

     int t=;

     while(x)

     {

         splay(x);

         son[x][]=t;

         ne[x]=fe[t];

         ud(x);

         t=x;

         x=fa[x];

     }

 }

 void reboot(int x)

 {

     acs(x);

     splay(x);

     torev(x);

 }

 void link(int x,int y,int z)

 {

     reboot(x);

     fa[x]=y;

     pe[x]=z;

 }

 void pick(int x,int y)

 {

     reboot(y);

     acs(x);

     splay(x);

 }

 void cut(int x,int y)

 {

     pick(x,y);

     son[x][]=fa[y]=;

     pe[x]=fe[x]=ne[y]=le[y]=;

     ud(x);

     ud(y);

 }

 int ask(int x,int y)

 {

     pick(x,y);

     return sum[x];

 }

 void change(int x,int y,int z)

 {

     pick(x,y);

     toch(x,z);

 }

 int main()

 {

     int i,o,x,y,z,xx,yy;

     srand(time());

     scanf("%*d%d%d",&n,&m);

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

         siz[i]=;

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

     {

         scanf("%d%d",&x,&y);

         link(x,y,++tot);

     }

     while(m--)

     {

         int cmd;

         scanf("%d",&cmd);

         if(cmd==)

         {

             scanf("%d%d%d%d",&x,&y,&xx,&yy);

             z=ask(x,y);

             cut(x,y);

             link(xx,yy,++tot);

             change(x,y,z);

         }

         if(cmd==)

         {

             cnt++;

             scanf("%d%d",&v1[cnt],&v2[cnt]);

             v[cnt]=rd();

             S^=v[cnt];

             change(v1[cnt],v2[cnt],v[cnt]);

         }

         if(cmd==)

             scanf("%d",&x),

             S^=v[x],

             change(v1[x],v2[x],v[x]);

         if(cmd==)

             scanf("%d%d",&x,&y),

             puts(ask(x,y)==S?"YES":"NO");

     }

     return ;

 }

巴特西

uoj207共价大爷游长沙

最新文章

热门文章