构建：像线性的莫队那样，依旧是按sqrt(n)为一块分块。
int dfs(int x){
int size=;
dfn[x]=++ind;
for (int i=;i<=;i++)
if (bin[i]<=deep[x])
fa[x][i]=fa[fa[x][i-]][i-];
else break;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur!=fa[x][]){
fa[pur][]=x;
deep[pur]=deep[x]+;
size+=dfs(pur);
if (size>=blo){
blonum++;
for (int k=;k<=size;k++)
belong[st[top--]]=blonum;
size=;
}
}
}
st[++top]=x;
return size+;
}
然后呢，我们可以发现一些树上莫队的性质：
用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 苹果树
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
#define Rep(i, l, r) for (int i = l; i <= r; ++i)
#define Req(i, l, r) for (int i = l; i >= r; --i)
#define N 100005
int tot,go[N],next[N],first[N],dfn[N],belong[N];
int st[N],res[N],n,m,x,y,fa[N][],bin[],col[N],ans,ind,deep[N],blo,blonum;
int top,pd[N],root;
struct op{
int u,v,id,a,b;
}q[N];
int p[N];
void insert(int x,int y){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
}
void add(int x,int y){
insert(x,y);
insert(y,x);
}
bool cmp(op q,op w){
if (belong[q.u]==belong[w.u]) return dfn[q.v]<dfn[w.v];
else return belong[q.u]<belong[w.u];
}
int dfs(int x){
int size=;
dfn[x]=++ind;
for (int i=;i<=;i++)
if (bin[i]<=deep[x])
fa[x][i]=fa[fa[x][i-]][i-];
else break;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur!=fa[x][]){
fa[pur][]=x;
deep[pur]=deep[x]+;
size+=dfs(pur);
if (size>=blo){
blonum++;
for (int k=;k<=size;k++)
belong[st[top--]]=blonum;
size=;
}
}
}
st[++top]=x;
return size+;
}
void reverse(int x){
if (pd[x]) {
p[col[x]]--;
pd[x]=;
if (p[col[x]]==) ans--;
}
else{
p[col[x]]++;
pd[x]=;
if (p[col[x]]==) ans++;
}
}
void solve(int u,int v){
while (u!=v){
if (deep[u]>deep[v]) reverse(u),u=fa[u][];
else reverse(v),v=fa[v][];
}
}
int lca(int x,int y){
if (deep[x]<deep[y]) std::swap(x,y);
int t=deep[x]-deep[y];
for (int i=;i>=;i--)
if (t&bin[i]){
x=fa[x][i];
}
for (int i=;i>=;i--)
if (fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
if (x==y) return x;
else return fa[x][];
}
int main(){
bin[]=;
for (int i=;i<;i++) bin[i]=bin[i-]*;
scanf("%d%d",&n,&m);
blo=sqrt(n);
for (int i=;i<=n;i++)
scanf("%d",&col[i]);
for (int i=;i<=n;i++){
scanf("%d%d",&x,&y);
if (x==)
root=y;
else
if (y==)
root=x;
else
add(x,y);
}
dfs(root);
blonum++;
while (top) belong[st[top--]]=blonum;
for (int i=;i<=m;i++){
scanf("%d%d",&q[i].u,&q[i].v);
if (dfn[q[i].u]>dfn[q[i].v]) std::swap(q[i].v,q[i].u);
scanf("%d%d",&q[i].a,&q[i].b);
q[i].id=i;
}
std::sort(q+,q++m,cmp);
int t=lca(q[].u,q[].v);
solve(q[].u,q[].v);
reverse(t);
res[q[].id]=ans;
if (p[q[].a]&&p[q[].b]&&q[].a!=q[].b) res[q[].id]--;
reverse(t);
for (int i=;i<=m;i++){
solve(q[i-].u,q[i].u);
solve(q[i-].v,q[i].v);
t=lca(q[i].u,q[i].v);
reverse(t);
res[q[i].id]=ans;
if (p[q[i].a]&&p[q[i].b]&&q[i].a!=q[i].b) res[q[i].id]--;
reverse(t);
}
for (int i=;i<=m;i++)
printf("%d\n",res[i]);
}
bzoj3052 WC糖果公园
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
#define Rep(i, l, r) for (int i = l; i <= r; ++i)
#define Req(i, l, r) for (int i = l; i >= r; --i)
#define N 200005
long long res[N];
long long pre[N],col[N],v[N],w[N],ans;
int belong[N],go[N],tot,first[N],next[N];
int deep[N],bin[],fa[N][],st[N],top,x,y,n,m,c1,c2,dfn[N],ind,blo,blonum;
int pd[N],p[N],qe,ty;
struct op{
int x,y,id,t;
long long pre;
}c[N],b[N];
bool cmp(op a,op b){
if (belong[a.x]==belong[b.x]&&belong[a.y]==belong[b.y]) return a.t<b.t;
else
if (belong[a.x]==belong[b.x]) return belong[a.y]<belong[b.y];
return belong[a.x]<belong[b.x];
}
void insert(int x,int y){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
}
void add(int x,int y){
insert(x,y);
insert(y,x);
}
int dfs(int x){
int size=;
dfn[x]=++ind;
for (int i=;i<=;i++)
if (deep[x]>=bin[i])
fa[x][i]=fa[fa[x][i-]][i-];
else break;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur!=fa[x][]){
fa[pur][]=x;
deep[pur]=deep[x]+;
size+=dfs(pur);
if (size>=blo){
blonum++;
for (int j=;j<=size;j++)
belong[st[top--]]=blonum;
size=;
}
}
}
st[++top]=x;
return size+;
}
void reverse(int x){
if (pd[x]){
ans-=w[p[col[x]]]*v[col[x]];
p[col[x]]--;
pd[x]=;
}
else{
pd[x]=;
p[col[x]]++;
ans+=w[p[col[x]]]*v[col[x]];
}
}
void change(int x,int y){
if (pd[x]){
reverse(x);
col[x]=y;
reverse(x);
}
else{
col[x]=y;
}
}
void solve(int x,int y){
while (x!=y){
if (deep[x]>deep[y]) reverse(x),x=fa[x][];
else reverse(y),y=fa[y][];
}
}
int lca(int x,int y){
if (deep[x]<deep[y]) std::swap(x,y);
int t=deep[x]-deep[y];
for (int i=;i>=;i--)
if (t&bin[i])
x=fa[x][i];
for (int i=;i>=;i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
if (x==y) return x;
else return fa[x][];
}
int main(){
//freopen("tx.txt","r",stdin);
bin[]=;
for (int i=;i<=;i++) bin[i]=bin[i-]*;
scanf("%d%d%d",&n,&m,&qe);
blo=pow(n,2.0/)*0.5;
for (int i=;i<=m;i++)
scanf("%lld",&v[i]);
for (int i=;i<=n;i++)
scanf("%lld",&w[i]);
for (int i=;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y);
}
for (int i=;i<=n;i++){
scanf("%lld",&col[i]);
pre[i]=col[i];
}
dfs();
//blonum++;
while (top) belong[st[top--]]=blonum;
for (int i=;i<=qe;i++){
scanf("%d",&ty);
if (!ty){
c1++;
scanf("%d%d",&c[c1].x,&c[c1].y);
c[c1].pre=pre[c[c1].x];
pre[c[c1].x]=c[c1].y;
}
else{
c2++;
scanf("%d%d",&b[c2].x,&b[c2].y);
b[c2].t=c1;
if (dfn[b[c2].x]>dfn[b[c2].y]) std::swap(b[c2].x,b[c2].y);
b[c2].id=c2;
}
}
std::sort(b+,b++c2,cmp);
for (int i=;i<=b[].t;i++)
change(c[i].x,c[i].y);
solve(b[].x,b[].y);
int t=lca(b[].x,b[].y);
reverse(t);
res[b[].id]=ans;
reverse(t);
for (int i=;i<=c2;i++){
for (int j=b[i-].t+;j<=b[i].t;j++)
change(c[j].x,c[j].y);
for (int j=b[i-].t;j>b[i].t;j--)
change(c[j].x,c[j].pre);
solve(b[i-].x,b[i].x);
solve(b[i-].y,b[i].y);
int t=lca(b[i].x,b[i].y);
reverse(t);
res[b[i].id]=ans;
reverse(t);
}
for (int i=;i<=c2;i++)
printf("%lld\n",res[i]);
}