[bzoj3282] Tree

bzoj 3282 传送门

洛谷 P3690 传送门

又是一道LCA裸题，操作很基础，不说了。

那就讲讲我是怎么在这道题卡了一个小时吧......

cut的时候，不仅要判断连通性，还要保证两点之间有直接相连的边，才能删边。

(line 129)我的错解：if(connected(x,y)) --> 正解：if(connected(x,y)&&(!s[x][1]))

还有就是判断连通性的时候，循环的边界，不能让y走到0。

(line 103)我的错解：for(;y;y=s[y][0]); --> 正解：for(;s[y][0];y=s[y][0]);

引以为戒吧。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define id(x) (s[f[x]][1]==x)
  5 using namespace std;
  6 
  7 int n,m;
  8 int s[300005][2],f[300005],sz[300005],sum[300005];
  9 int v[300005];
 10 bool rt[300005],rev[300005];
 11 
 12 void pushup(int p)
 13 {
 14     sz[p]=sz[s[p][0]]+sz[s[p][1]]+1;
 15     sum[p]=sum[s[p][0]]^sum[s[p][1]]^v[p];
 16 }
 17 
 18 void reverse(int p)
 19 {
 20     swap(s[p][0],s[p][1]);
 21     rev[p]^=1;
 22 }
 23 
 24 void pushdown(int p)
 25 {
 26     if(!rev[p])return;
 27     reverse(s[p][0]);
 28     reverse(s[p][1]);
 29     rev[p]=0;
 30 }
 31 
 32 int st[300005];
 33 
 34 void down(int p)
 35 {
 36     int tp=0;
 37     while(!rt[p])st[++tp]=p,p=f[p];
 38     for(pushdown(p);tp;pushdown(st[tp--]));
 39 }
 40 
 41 void rotate(int p)
 42 {
 43     int k=id(p);
 44     int fa=f[p];
 45     if(rt[fa])rt[p]=1,rt[fa]=0;
 46     else s[f[fa]][id(fa)]=p;
 47     s[fa][k]=s[p][!k];
 48     s[p][!k]=fa;
 49     f[p]=f[fa];
 50     f[fa]=p;
 51     f[s[fa][k]]=fa;
 52     pushup(fa);
 53     pushup(p);
 54 }
 55 
 56 void splay(int p)
 57 {
 58     down(p);
 59     while(!rt[p])
 60     {
 61         int fa=f[p];
 62         if(rt[fa])
 63         {
 64             rotate(p);
 65             return;
 66         }
 67         if(id(p)^id(fa))rotate(p);
 68         else rotate(fa);
 69         rotate(p);
 70     }
 71 }
 72 
 73 void access(int p)
 74 {
 75     int son=0;
 76     while(p)
 77     {
 78         splay(p);
 79         rt[s[p][1]]=1,rt[son]=0;
 80         s[p][1]=son;
 81         pushup(p);
 82         son=p,p=f[p];
 83     }
 84 }
 85 
 86 void mtr(int p)
 87 {
 88     access(p);
 89     splay(p);
 90     reverse(p);
 91 }
 92 
 93 void isolate(int x,int y)
 94 {
 95     mtr(x);
 96     access(y);
 97     splay(y);
 98 }
 99 
100 int connected(int x,int y)
101 {
102     isolate(x,y);
103     for(;s[y][0];y=s[y][0]);
104     return x==y;
105 }
106 
107 int main()
108 {
109     scanf("%d%d",&n,&m);
110     for(int i=1;i<=n;i++)
111     {
112         scanf("%d",&v[i]);
113         sum[i]=v[i];
114         sz[i]=rt[i]=1;
115     }
116     for(int i=1;i<=m;i++)
117     {
118         int op,x,y;
119         scanf("%d%d%d",&op,&x,&y);
120         if(op==0)
121         {
122             isolate(x,y);
123             printf("%d
",sum[y]);
124         }
125         if(op==1)
126             if(!connected(x,y))
127                 mtr(x),f[x]=y;
128         if(op==2)
129             if(connected(x,y)&&(!s[x][1]))
130                 rt[x]=1,f[x]=s[y][0]=0,pushup(y);
131         if(op==3)
132         {
133             splay(x);
134             v[x]=y;
135             pushup(x);
136         }
137     }
138     return 0;
139 }