bzoj 4771 七彩树
Description
给定一棵 (n) 个结点的以 (1) 为根的树，每个点有颜色。每次询问给定 (u,d)，你要求出在以 为根的子树 (u) 内所有与 (u) 距离不超过 (d) 的点中不同颜色个数，强制在线。
(n,qle 2 imes 10^5)
Solution
首先容易想到的是对每个节点用线段树 (T_1) 维护距离 (le d) 的子孙的颜色总数，然后使用线段树合并算法。但合并时对于新增某些颜色的情况难以维护，这是因为无法判定这些颜色是否出现过。
于是我们对每个节点用另一棵线段树 (T_2) 维护每个颜色在其子树中所有出现位置中最浅的一个。这时容易线段树合并维护的。当合并 (u) 与 (v) 时，先合并它们的 (T_2)，每当某个颜色的最浅出现位置被修改时，才在 (T_1) 中进行修改。这样一来就可以 (mathcal O((n+q)log n) 的完成此题了。
Code
#include <iostream>
#include <cstdio>
#include <math.h>
inline int read(){
int s=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
return s*f;
}
using namespace std;
const int N=500010,M=N<<5,inf=1e9;
struct Edge{int to,next;}e[N<<1];
int head[N],ecnt;
inline void adde(int u,int v){e[++ecnt].next=head[u];head[u]=ecnt;e[ecnt].to=v;}
int T,n,m,c[N];
struct Seg_Tree1{
int rt[N],cnt[M],ls[M],rs[M],inde;
inline void init(){inde=0;fill(rt+1,rt+1+n,0);}
#define mid ((l+r)>>1)
void modify(int &id,int pre,int l,int r,int pos,int val){
id=++inde;cnt[id]=cnt[pre]+val;ls[id]=ls[pre],rs[id]=rs[pre];
if(l==r)return;
if(pos<=mid)modify(ls[id],ls[pre],l,mid,pos,val);
else modify(rs[id],rs[pre],mid+1,r,pos,val);
}
int merge(int x,int y){
if(!x||!y)return x+y;
int p=++inde;
cnt[p]=cnt[x]+cnt[y];
ls[p]=merge(ls[x],ls[y]);
rs[p]=merge(rs[x],rs[y]);
return p;
}
int query(int id,int l,int r,int L,int R){
if(!id)return 0;
if(L<=l&&r<=R)return cnt[id];
int ret=0;
if(L<=mid)ret+=query(ls[id],l,mid,L,R);
if(R>mid)ret+=query(rs[id],mid+1,r,L,R);
return ret;
}
}T1;
struct Seg_Tree2{
int rt[N],mn[M],ls[M],rs[M],inde;
inline void init(){inde=0;fill(rt+1,rt+1+n,0);mn[0]=inf;}
#define mid ((l+r)>>1)
void modify(int &id,int pre,int l,int r,int pos,int val){
id=++inde;ls[id]=ls[pre],rs[id]=rs[pre];
if(l==r){mn[id]=min(mn[pre],val);return;}
if(pos<=mid)modify(ls[id],ls[pre],l,mid,pos,val);
else modify(rs[id],rs[pre],mid+1,r,pos,val);
}
int merge(int x,int y,int l,int r,int u){
if(!x||!y)return x+y;
int p=++inde;
if(l==r){
mn[p]=min(mn[x],mn[y]);T1.modify(T1.rt[u],T1.rt[u],1,n,max(mn[x],mn[y]),-1);
return p;
}
ls[p]=merge(ls[x],ls[y],l,mid,u);
rs[p]=merge(rs[x],rs[y],mid+1,r,u);
return p;
}
}T2;
int dep[N],mxdep;
void dfs(int u,int fa){
dep[u]=dep[fa]+1;mxdep=max(mxdep,dep[u]);
T1.modify(T1.rt[u],T1.rt[u],1,n,dep[u],1);
T2.modify(T2.rt[u],T2.rt[u],1,n,c[u],dep[u]);
for(int i=head[u],v;i;i=e[i].next){
v=e[i].to;dfs(v,u);T1.rt[u]=T1.merge(T1.rt[u],T1.rt[v]);
T2.rt[u]=T2.merge(T2.rt[u],T2.rt[v],1,n,u);
}
}
int x,d,lastans;
inline void init(){
lastans=ecnt=mxdep=0;fill(head+1,head+1+n,0);
T1.init();T2.init();
}
int main(){
T=read();
while(T--){
n=read();m=read();
init();
for(int i=1;i<=n;++i)c[i]=read();
for(int i=2,fa;i<=n;++i)fa=read(),adde(fa,i);
dfs(1,0);
while(m--){
x=read()^lastans;d=read()^lastans;
printf("%d
",lastans=T1.query(T1.rt[x],1,n,dep[x],min(dep[x]+d,mxdep)));
}
}
return 0;
}