题目描述
给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v)，你需要回答u xor lastans和v这两个节点间有多少种不同的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。
输入格式
第一行两个整数N,M。
第二行有N个整数，其中第i个整数表示点i的权值。
后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。
最后M行每行两个整数(u,v)，表示一组询问。
数据范围是N<=40000 M<=100000 点权在int范围内
输出格式
M行，表示每个询问的答案。
-
题解
- 树上莫队；
- 如果不要求强制在线的话比较传统；
- 强制在线有点麻烦：
- 对树按深度分块，当一个点向下的深度超过$\sqrt{N}$就分一块；
- 这样分块保证了深度和块的数量在$O(\sqrt{N})$内，并且每一个块都是一颗子树；
- 预处理每个块的根对其他所有点的答案，这是$O(n\sqrt{N})$的时间和空间的；
- 考虑一个询问$u,v$如果在同一个块里则暴力查询;$O(\sqrt{N})$
- 否则假设$u$的根比$v$的根要深，否则交换；
- 利用预处理得到$(root_{u},v)$的答案$O(1)$，暴力查询$u$到$root_{u})$的颜色$O(\sqrt{N})$；
- 只需要查询某个颜色是否出现过；
- 可持久化块状链表记录$u$到原树的根链上的每个颜色出现的最大深度；$O(\sqrt{N})$
- 枚举的颜色没有出现过即查询颜色的最大深度一定小于$lca$的深度；
- 可持久化块状链表：
- 对颜色分块，记录每个历史版本每个块的起点；
- 插入的时候暴力复制上一个版本的起点，暴力新建一个修改位置的块并更新起点
#include<bits/stdc++.h>
using namespace std;
const int N=,M=;
int n,m,o=,hd[N],F[N],num[N],tot,sub[N],dep[N],rt,c[N],ans;
int B,sum[M][N],bl[N],cnt,len[N],Rt[M],sta[N],top;
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
struct Edge{int v,nt;}E[N<<];
char gc(){
static char*p1,*p2,s[];
if(p1==p2)p2=(p1=s)+fread(s,,,stdin);
return(p1==p2)?EOF:*p1++;
}
int rd(){
int x=,f=; char c=gc();
while(c<''||c>''){if(c=='-')f=-;c=gc();}
while(c>=''&&c<='')x=(x<<)+(x<<)+c-'',c=gc();
return x*f;
}
void adde(int u,int v){
E[o]=(Edge){v,hd[u]};hd[u]=o++;
E[o]=(Edge){u,hd[v]};hd[v]=o++;
}
namespace Block{
int l[N][M],a[N*M],Cnt,bl[N],B,st[M],ed[M],sz;
void init(){
B=sqrt(tot)+;
for(int i=;i<=tot;++i)bl[i]=(i-)/B+,a[i]=-;
sz=bl[tot];
for(int i=;i<=sz;++i){
l[][i]=st[i]=ed[i-]+;
ed[i]=ed[i-]+B;
}
ed[sz]=Cnt=tot;
}
int que(int u,int x){return a[l[u][bl[x]]+(x-)%B];}
void ins(int u,int x){
for(int i=;i<=sz;++i)l[u][i]=l[F[u]][i];
int len=ed[bl[x]]-st[bl[x]],tmp=l[u][bl[x]],pre=Cnt;
for(int i=;i<=len;++i)a[++Cnt]=a[tmp+i];
a[pre++(x-)%B]=dep[u];
l[u][bl[x]]=pre+;
}
}
void upd(int x,int y){
if((num[x]==)^(num[x]+y==))tot+=y;
num[x]+=y;
}
void dfs1(int u,int fa){
upd(c[u],);
sum[cnt][u]=tot;
for(int i=hd[u];i;i=E[i].nt)if(E[i].v!=fa)dfs1(E[i].v,u);
upd(c[u],-);
}
void dfs(int u,int fa){
int x=c[u];
F[u]=fa;
Block::ins(u,x);
sta[++top]=u;
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==fa)continue;
dep[v]=dep[u]+;
dfs(v,u);
len[u]=max(len[v]+,len[u]);
}
if(len[u]>=B||u==){
len[u]=-;
Rt[++cnt]=u;
int v;do{
bl[v=sta[top--]]=cnt;
}while(v!=u);
dfs1(u,);
}
}
namespace LCA{
int son[N],tp[N],sz[N],F[N];
void dfs1(int u,int fa){
sz[u]=;son[u]=;F[u]=fa;
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==fa)continue;
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}
}
void dfs2(int u,int T){
tp[u]=T;
if(son[u])dfs2(son[u],T);
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==F[u]||v==son[u])continue;
dfs2(v,v);
}
}
int ask(int u,int v){
int tu=tp[u],tv=tp[v];
while(tu!=tv){
if(dep[tu]<dep[tv])v=F[tv],tv=tp[v];
else u=F[tu],tu=tp[u];
}
return dep[u]<dep[v]?u:v;
}
void init(){dfs1(,);dfs2(,);}
}
void query1(int u,int v){
int x=Rt[bl[u]],y=Rt[bl[v]],dz=dep[LCA::ask(u,v)];
if(dep[x]<dep[y])swap(x,y),swap(u,v);
ans=sum[bl[u]][v];
for(int w=u;w!=x;w=F[w]){
int d = max(Block::que(x,c[w]),Block::que(v,c[w]));
if(!num[c[w]]&&d<dz)num[c[w]]=,ans++;
}
for(int w=u;w!=x;w=F[w])num[c[w]]=;
printf("%d\n",ans);
}
void query2(int u,int v){
int dz=dep[LCA::ask(u,v)];
ans=;
for(int w=u;dep[w]>=dz;w=F[w])if(!(num[c[w]]++))ans++;
for(int w=v;dep[w]>=dz;w=F[w])if(!(num[c[w]]++))ans++;
for(int w=u;dep[w]>=dz;w=F[w])num[c[w]]=;
for(int w=v;dep[w]>=dz;w=F[w])num[c[w]]=;
printf("%d\n",ans);
}
int find(int x){
int l=,r=tot,mid;
while(l<r){
if(x<=sub[mid=l+r>>])r=mid;
else l=mid+;
}
return l;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("bzoj2589.in","r",stdin);
freopen("bzoj2589.out","w",stdout);
#endif
n=rd();m=rd();
B=sqrt(n)+;
for(int i=,x;i<=n;++i)c[i]=sub[i]=rd();
for(int i=,u,v;i<n;++i)adde(rd(),rd());
tot=n;sort(sub+,sub+tot+);
tot=unique(sub+,sub+tot+)-sub-;
for(int i=;i<=n;++i)c[i]=lower_bound(sub+,sub+tot+,c[i])-sub;
Block::init();
dep[]=-;
tot=;dfs(,);
LCA::init();
for(int i=,x,y;i<=m;++i){
x=rd()^ans,y=rd();
if(bl[x]!=bl[y])query1(x,y);
else query2(x,y);
}
return ;
}bzoj2589