传送门
一道树上莫队。
先用跟bzoj1086一样的方法给树分块。
分完之后就可以莫队了。
但是两个询问之间如何转移呢？
感觉很难受啊。
我们定义S(u,v)" role="presentation" style="position: relative;">S(u,v)S(u,v)表示u->v这条路径的点集，T(u,v)" role="presentation" style="position: relative;">T(u,v)T(u,v)表示S(u,v)" role="presentation" style="position: relative;">S(u,v)S(u,v) xor" role="presentation" style="position: relative;">xorxor lca(u,v)" role="presentation" style="position: relative;">lca(u,v)lca(u,v)，同时我们令上一个询问是S(predu,predv)" role="presentation" style="position: relative;">S(predu,predv)S(predu,predv)。
对于T(u,v)" role="presentation" style="position: relative;">T(u,v)T(u,v)有一个恒等式：
T(u,v)=S(root,u)" role="presentation" style="position: relative;">T(u,v)=S(root,u)T(u,v)=S(root,u) xor" role="presentation" style="position: relative;">xorxor S(root,v)" role="presentation" style="position: relative;">S(root,v)S(root,v)
因此有：
T(predu,predv)=S(root,predu)" role="presentation" style="position: relative;">T(predu,predv)=S(root,predu)T(predu,predv)=S(root,predu) xor" role="presentation" style="position: relative;">xorxor S(root,predv)" role="presentation" style="position: relative;">S(root,predv)S(root,predv)
因此有：
T(u,v)" role="presentation" style="position: relative;">T(u,v)T(u,v) xor" role="presentation" style="position: relative;">xorxor T(predu,predv)=S(root,u)" role="presentation" style="position: relative;">T(predu,predv)=S(root,u)T(predu,predv)=S(root,u) xor" role="presentation" style="position: relative;">xorxor S(root,v)" role="presentation" style="position: relative;">S(root,v)S(root,v) xor" role="presentation" style="position: relative;">xorxor S(root,predu)" role="presentation" style="position: relative;">S(root,predu)S(root,predu) xor" role="presentation" style="position: relative;">xorxor S(root,predv)" role="presentation" style="position: relative;">S(root,predv)S(root,predv)
因此有：
T(u,v)=T(predu,predv)" role="presentation" style="position: relative;">T(u,v)=T(predu,predv)T(u,v)=T(predu,predv) xor" role="presentation" style="position: relative;">xorxor T(predu,v)" role="presentation" style="position: relative;">T(predu,v)T(predu,v) xor" role="presentation" style="position: relative;">xorxor T(u,predv)" role="presentation" style="position: relative;">T(u,predv)T(u,predv)
那么更新就比较容易了。
代码：
#include<bits/stdc++.h>
#define N 100005
#define sig 24
using namespace std;
int n,m,rt,sum,ans[N],blo[N],dfn[N],dep[N],first[N],cnt,blos,top,fa[N][sig],mul[N],block,tot,stk[N],tim[N],col[N];
bool vis[N];
struct edge{int v,next;}e[N<<1];
struct Q{int u,v,a,b,id;}q[N];
inline bool cmp(Q a,Q b){return blo[a.u]==blo[b.u]?dfn[a.v]<dfn[b.v]:blo[a.u]<blo[b.u];}
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline void dfs(int p){
dfn[p]=++tot,dep[p]=dep[fa[p][0]]+1;
int tmp=top;
for(int i=1;i<sig;++i)
if(dep[p]<mul[i])break;
else fa[p][i]=fa[fa[p][i-1]][i-1];
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==fa[p][0])continue;
fa[v][0]=p,dfs(v);
if(top-tmp>=block){
++blos;
while(top!=tmp)blo[stk[top--]]=blos;
}
}
stk[++top]=p;
}
inline int lca(int x,int y){
if(dep[x]<dep[y])x^=y,y^=x,x^=y;
int tmp=dep[x]-dep[y];
for(int i=0;i<sig;++i)if(tmp&(1<<i))x=fa[x][i];
if(x==y)return x;
for(int i=sig-1;~i;--i)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
inline void update(int x){
if(vis[x]){
vis[x]=0,--tim[col[x]];
if(tim[col[x]]==0)--sum;
}
else{
vis[x]=1,++tim[col[x]];
if(tim[col[x]]==1)++sum;
}
}
inline void reverse(int x,int y){
while(x!=y){
if(dep[x]<dep[y])x^=y,y^=x,x^=y;
update(x),x=fa[x][0];
}
}
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int main(){
n=read(),m=read(),mul[0]=1,block=sqrt(n);
for(int i=1;i<=n;++i)col[i]=read();
for(int i=1;i<=n;++i){
int u=read(),v=read();
if(!u||!v)rt=u+v;
else add(u,v),add(v,u);
}
for(int i=1;i<sig;++i)mul[i]=mul[i-1]<<1;
dfs(rt),++blos;
while(top)blo[stk[top--]]=blos;
for(int i=1;i<=m;++i){
q[i].u=read(),q[i].v=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
if(dfn[q[i].u]>dfn[q[i].v])q[i].u^=q[i].v,q[i].v^=q[i].u,q[i].u^=q[i].v;
}
sort(q+1,q+m+1,cmp);
int Lca=lca(q[1].u,q[1].v);
reverse(q[1].u,q[1].v),update(Lca),ans[q[1].id]=sum;
if(q[1].a!=q[1].b&&tim[q[1].a]&&tim[q[1].b])--ans[q[1].id];
for(int i=2;i<=m;++i){
update(Lca),reverse(q[i-1].u,q[i].u),reverse(q[i-1].v,q[i].v);
Lca=lca(q[i].u,q[i].v),update(Lca),ans[q[i].id]=sum;
if(q[i].a!=q[i].b&&tim[q[i].a]&&tim[q[i].b])--ans[q[i].id];
}
for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
return 0;
}