树上莫队 wowow

构建：像线性的莫队那样，依旧是按sqrt(n)为一块分块。

 1 int dfs(int x){
 2     int size=0;
 3     dfn[x]=++ind;
 4     for (int i=1;i<=16;i++)
 5      if (bin[i]<=deep[x])
 6      fa[x][i]=fa[fa[x][i-1]][i-1];
 7      else break;
 8     for (int i=first[x];i;i=next[i]){
 9         int pur=go[i];
10         if (pur!=fa[x][0]){
11             fa[pur][0]=x;
12             deep[pur]=deep[x]+1;
13             size+=dfs(pur);
14             if (size>=blo){
15                 blonum++;
16                 for (int k=1;k<=size;k++)
17                  belong[st[top--]]=blonum;
18                 size=0; 
19             }
20         }
21     }
22     st[++top]=x;
23     return size+1;
24 }

然后呢，我们可以发现一些树上莫队的性质：

用S(v, u)代表 v到u的路径上的结点的集合。

用root来代表根结点，用lca(v, u)来代表v、u的最近公共祖先。

那么

S(v, u) = S(root, v) xor S(root, u) xor lca(v, u)

其中xor是集合的对称差。

简单来说就是节点出现两次消掉。

lca很讨厌，于是再定义

T(v, u) = S(root, v) xor S(root, u)

观察将curV移动到targetV前后T(curV, curU)变化：

T(curV, curU) = S(root, curV) xor S(root, curU)

T(targetV, curU) = S(root, targetV) xor S(root, curU)

取对称差：

T(curV, curU) xor T(targetV, curU)= (S(root, curV) xor S(root, curU)) xor (S(root, targetV) xor S(root, curU))

由于对称差的交换律、结合律：

T(curV, curU) xor T(targetV, curU)= S(root, curV) xorS(root, targetV)

两边同时xor T(curV, curU)：

T(targetV, curU)= T(curV, curU) xor S(root, curV) xor S(root, targetV)

即

T(targetV, curU)= T(curV, curU) xor T(curV, targetV)

也就是说，更新的时候，xor T(curV, targetV)就行了。

即，对curV到targetV路径(除开lca(curV, targetV))上的结点，将它们的存在性取反即可。

按照以上方式，我们就可以每次从u1走到u2,v1走到v2，然后要求query的时候对他们的公共祖先的存在性取反，然后求完答案后再取反回去。

bzoj3757 苹果树

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <string>
  6 #include <queue>
  7 #include <stack>
  8 #include <cmath>
  9 #include <map>
 10 #include <vector>
 11 #include <functional>
 12 #include <ctime>
 13 #include <cstdlib>
 14 #include <sstream>
 15 #include <set>
 16 #include <deque>
 17 #define Rep(i, l, r) for (int i = l; i <= r; ++i)
 18 #define Req(i, l, r) for (int i = l; i >= r; --i)
 19 #define N 100005
 20 int tot,go[N],next[N],first[N],dfn[N],belong[N];
 21 int st[N],res[N],n,m,x,y,fa[N][20],bin[20],col[N],ans,ind,deep[N],blo,blonum;
 22 int top,pd[N],root;
 23 struct op{
 24     int u,v,id,a,b;
 25 }q[N];
 26 int p[N];
 27 void insert(int x,int y){
 28     tot++;
 29     go[tot]=y;
 30     next[tot]=first[x];
 31     first[x]=tot;
 32 }
 33 void add(int x,int y){
 34     insert(x,y);
 35     insert(y,x);
 36 }
 37 bool cmp(op q,op w){
 38     if (belong[q.u]==belong[w.u]) return dfn[q.v]<dfn[w.v];
 39     else return belong[q.u]<belong[w.u];
 40 }
 41 int dfs(int x){
 42     int size=0;
 43     dfn[x]=++ind;
 44     for (int i=1;i<=16;i++)
 45      if (bin[i]<=deep[x])
 46      fa[x][i]=fa[fa[x][i-1]][i-1];
 47      else break;
 48     for (int i=first[x];i;i=next[i]){
 49         int pur=go[i];
 50         if (pur!=fa[x][0]){
 51             fa[pur][0]=x;
 52             deep[pur]=deep[x]+1;
 53             size+=dfs(pur);
 54             if (size>=blo){
 55                 blonum++;
 56                 for (int k=1;k<=size;k++)
 57                  belong[st[top--]]=blonum;
 58                 size=0; 
 59             }
 60         }
 61     }
 62     st[++top]=x;
 63     return size+1;
 64 }
 65 void reverse(int x){
 66     if (pd[x]) {
 67         p[col[x]]--;
 68         pd[x]=0;
 69         if (p[col[x]]==0) ans--;
 70     }
 71     else{
 72         p[col[x]]++;
 73         pd[x]=1;
 74         if (p[col[x]]==1) ans++;
 75     }
 76 }
 77 void solve(int u,int v){
 78     while (u!=v){
 79         if (deep[u]>deep[v]) reverse(u),u=fa[u][0];
 80         else reverse(v),v=fa[v][0];
 81     }
 82 }
 83 int lca(int x,int y){
 84     if (deep[x]<deep[y]) std::swap(x,y);
 85     int t=deep[x]-deep[y];
 86     for (int i=19;i>=0;i--)
 87      if (t&bin[i]){
 88         x=fa[x][i];
 89      }
 90     for (int i=19;i>=0;i--)
 91      if (fa[x][i]!=fa[y][i]){
 92         x=fa[x][i];
 93         y=fa[y][i];
 94      } 
 95     if (x==y) return x;
 96     else return fa[x][0]; 
 97 }
 98 int main(){
 99     bin[0]=1;
100     for (int i=1;i<20;i++) bin[i]=bin[i-1]*2;
101     scanf("%d%d",&n,&m);
102     blo=sqrt(n);
103     for (int i=1;i<=n;i++)
104      scanf("%d",&col[i]);
105     for (int i=1;i<=n;i++){
106         scanf("%d%d",&x,&y);
107         if (x==0)
108             root=y;
109         else
110         if (y==0)
111             root=x;
112         else   
113         add(x,y);
114     } 
115     dfs(root);
116     blonum++;
117     while (top) belong[st[top--]]=blonum;
118     for (int i=1;i<=m;i++){
119         scanf("%d%d",&q[i].u,&q[i].v);
120         if (dfn[q[i].u]>dfn[q[i].v]) std::swap(q[i].v,q[i].u);
121         scanf("%d%d",&q[i].a,&q[i].b);
122         q[i].id=i;
123     }
124     std::sort(q+1,q+1+m,cmp);
125     int t=lca(q[1].u,q[1].v);
126     solve(q[1].u,q[1].v);
127     reverse(t);
128     res[q[1].id]=ans;
129     if (p[q[1].a]&&p[q[1].b]&&q[1].a!=q[1].b) res[q[1].id]--;
130     reverse(t);
131     for (int i=2;i<=m;i++){
132         solve(q[i-1].u,q[i].u);
133         solve(q[i-1].v,q[i].v);
134         t=lca(q[i].u,q[i].v);
135         reverse(t);
136         res[q[i].id]=ans;
137         if (p[q[i].a]&&p[q[i].b]&&q[i].a!=q[i].b) res[q[i].id]--;
138         reverse(t);
139     }
140     for (int i=1;i<=m;i++)
141      printf("%d
",res[i]);
142 }

bzoj3052 WC糖果公园

  1  
  2 #include <cstdio>
  3 #include <iostream>
  4 #include <cstring>
  5 #include <algorithm>
  6 #include <string>
  7 #include <queue>
  8 #include <stack>
  9 #include <cmath>
 10 #include <map>
 11 #include <vector>
 12 #include <functional>
 13 #include <ctime>
 14 #include <cstdlib>
 15 #include <sstream>
 16 #include <set>
 17 #include <deque>
 18 #define Rep(i, l, r) for (int i = l; i <= r; ++i)
 19 #define Req(i, l, r) for (int i = l; i >= r; --i)
 20 #define N 200005
 21 long long res[N];
 22 long long pre[N],col[N],v[N],w[N],ans;
 23 int belong[N],go[N],tot,first[N],next[N];
 24 int deep[N],bin[20],fa[N][17],st[N],top,x,y,n,m,c1,c2,dfn[N],ind,blo,blonum;
 25 int pd[N],p[N],qe,ty;
 26 struct op{
 27     int x,y,id,t;
 28     long long pre;
 29 }c[N],b[N];
 30 bool cmp(op a,op b){
 31     if (belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y]) return a.t<b.t;
 32     else
 33     if (belong[a.x]==belong[b.x]) return belong[a.y]<belong[b.y];
 34     return belong[a.x]<belong[b.x];
 35 }
 36 void insert(int x,int y){
 37     tot++;
 38     go[tot]=y;
 39     next[tot]=first[x];
 40     first[x]=tot;
 41 }
 42 void add(int x,int y){
 43     insert(x,y);
 44     insert(y,x);
 45 }
 46 int dfs(int x){
 47     int size=0;
 48     dfn[x]=++ind;
 49     for (int i=1;i<=16;i++)
 50      if (deep[x]>=bin[i])
 51       fa[x][i]=fa[fa[x][i-1]][i-1];
 52      else break; 
 53     for (int i=first[x];i;i=next[i]){
 54         int pur=go[i];
 55         if (pur!=fa[x][0]){
 56             fa[pur][0]=x;
 57             deep[pur]=deep[x]+1;
 58             size+=dfs(pur);
 59             if (size>=blo){
 60                 blonum++;
 61                 for (int j=1;j<=size;j++)
 62                  belong[st[top--]]=blonum;
 63                 size=0; 
 64             }
 65         }
 66     }  
 67     st[++top]=x;
 68     return size+1;
 69 }
 70 void reverse(int x){
 71     if (pd[x]){
 72         ans-=w[p[col[x]]]*v[col[x]];
 73         p[col[x]]--;
 74         pd[x]=0;
 75     }
 76     else{
 77         pd[x]=1;
 78         p[col[x]]++;
 79         ans+=w[p[col[x]]]*v[col[x]];
 80     }
 81 }
 82 void change(int x,int y){
 83     if (pd[x]){
 84         reverse(x);
 85         col[x]=y;
 86         reverse(x);
 87     }
 88     else{
 89         col[x]=y;
 90     }
 91 }
 92 void solve(int x,int y){
 93     while (x!=y){
 94         if (deep[x]>deep[y]) reverse(x),x=fa[x][0];
 95         else reverse(y),y=fa[y][0];
 96     }
 97 }
 98 int lca(int x,int y){
 99     if (deep[x]<deep[y]) std::swap(x,y);
100     int t=deep[x]-deep[y];
101     for (int i=16;i>=0;i--)
102      if (t&bin[i])
103       x=fa[x][i];
104     for (int i=16;i>=0;i--)
105      if (fa[x][i]!=fa[y][i])
106       x=fa[x][i],y=fa[y][i];
107     if (x==y) return x;
108     else return fa[x][0];    
109 }
110 int main(){
111     //freopen("tx.txt","r",stdin);
112     bin[0]=1;
113     for (int i=1;i<=17;i++) bin[i]=bin[i-1]*2;
114     scanf("%d%d%d",&n,&m,&qe);
115     blo=pow(n,2.0/3)*0.5;
116     for (int i=1;i<=m;i++)
117      scanf("%lld",&v[i]);
118     for (int i=1;i<=n;i++)
119      scanf("%lld",&w[i]);
120     for (int i=1;i<n;i++){
121         scanf("%d%d",&x,&y);
122         add(x,y);
123     }  
124     for (int i=1;i<=n;i++){
125      scanf("%lld",&col[i]);
126      pre[i]=col[i];
127      }
128     dfs(1); 
129     //blonum++;
130     while (top) belong[st[top--]]=blonum;
131     for (int i=1;i<=qe;i++){
132         scanf("%d",&ty);
133         if (!ty){
134             c1++;
135             scanf("%d%d",&c[c1].x,&c[c1].y);
136             c[c1].pre=pre[c[c1].x];
137             pre[c[c1].x]=c[c1].y;
138         }
139         else{
140             c2++;
141             scanf("%d%d",&b[c2].x,&b[c2].y);
142             b[c2].t=c1;
143             if (dfn[b[c2].x]>dfn[b[c2].y]) std::swap(b[c2].x,b[c2].y);
144             b[c2].id=c2;
145         }
146     }
147     std::sort(b+1,b+1+c2,cmp);
148     for (int i=1;i<=b[1].t;i++)
149      change(c[i].x,c[i].y);
150     solve(b[1].x,b[1].y);
151     int t=lca(b[1].x,b[1].y);
152     reverse(t);
153     res[b[1].id]=ans;
154     reverse(t);
155     for (int i=2;i<=c2;i++){
156         for (int j=b[i-1].t+1;j<=b[i].t;j++)
157          change(c[j].x,c[j].y);
158         for (int j=b[i-1].t;j>b[i].t;j--)
159          change(c[j].x,c[j].pre); 
160         solve(b[i-1].x,b[i].x);
161         solve(b[i-1].y,b[i].y);
162         int t=lca(b[i].x,b[i].y);
163         reverse(t); 
164         res[b[i].id]=ans;
165         reverse(t);
166     } 
167     for (int i=1;i<=c2;i++)
168      printf("%lld
",res[i]);
169 }
170