bzoj 4771 七彩树

主席树.

• 询问的点要求在子树 $x$ 内,并且 $dep\leq dep_x+d$ ,这样就有 $dfn,dep$ 上的两维限制,所以可以用主席树把符合条件的点抠出来.
• 只需要考虑怎么计算不同颜色的种数.对于一种颜色,可以在每个点的位置让权值 $+1$ ,而在 $LCA$ 处让权值 $-1$ .只需要处理 $dfs$ 序相邻的两个点的 $LCA$ (因为最深)就可以保证询问子树时贡献不会被重复计算了.

Copy

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
struct PreSegtree
{
	int idx;
	void init(){idx=0;Tree[0].siz=Tree[0].ls=Tree[0].rs=0;}
	struct node
	{
		int ls,rs,siz;
	}Tree[MAXN*50];
#define root Tree[o]
	void insert(int &o,int lst,int l,int r,int pos,int c)
	{
		o=++idx;
		root=Tree[lst];
		root.siz+=c;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		if(pos<=mid)
			insert(root.ls,Tree[lst].ls,l,mid,pos,c);
		else
			insert(root.rs,Tree[lst].rs,mid+1,r,pos,c);
	}
	int query(int o,int l,int r,int L,int R)
	{
		if(L>r || l>R || !o)
			return 0;
		if(L<=l && r<=R)
			return root.siz;
		int mid=(l+r)>>1;
		int res=0;
		if(L<=mid)
			res+=query(root.ls,l,mid,L,R);
		if(R>mid)
			res+=query(root.rs,mid+1,r,L,R);
		return res;
	}
}T;
int rt[MAXN];
int ecnt=0,head[MAXN],to[MAXN],nx[MAXN];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int n,m;
int dfnidx=0,dfn[MAXN],rnk[MAXN],siz[MAXN],dep[MAXN];
int fa[MAXN][20],Log[MAXN];
int LCA(int x,int y)
{
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=Log[dep[x]-dep[y]];i>=0;--i)
		if(dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
	if(x==y)
		return x;
	for(int i=Log[dep[x]];i>=0;--i)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
void dfs(int u)
{
	dfn[u]=++dfnidx;
	rnk[dfnidx]=u;
	siz[u]=1;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		dep[v]=dep[u]+1;
		dfs(v);
		siz[u]+=siz[v];
	}
}
set<int> S[MAXN];
set<int>::iterator it;
void init()
{
	ecnt=0;
	dfnidx=0;
	T.init();
	memset(head,0,sizeof head);
	memset(rt,0,sizeof rt);
	memset(fa,0,sizeof fa);
	dep[1]=1;
}
int pd[MAXN],v[MAXN];
bool cmp(int x,int y)
{
	return dep[x]<dep[y];
}
void solve()
{
	int lastans=0;
	n=read(),m=read();
	for(int i=1;i<=n;++i)
	{
		v[i]=read();
		S[i].clear();
		pd[i]=i;
	}
	for(int i=2;i<=n;++i)
	{
		fa[i][0]=read();
		addedge(fa[i][0],i);
	}
	dfs(1);
	for(int j=1;j<=Log[n];++j)
		for(int i=1;i<=n;++i)
			fa[i][j]=fa[fa[i][j-1]][j-1];
	sort(pd+1,pd+1+n,cmp);
	for(int i=1;i<=n;++i)
	{
		int j=pd[i];
		int a=0,b=0;
		it=S[v[j]].lower_bound(dfn[j]);
		T.insert(rt[dep[j]],rt[dep[pd[i-1]]],1,n,dfn[j],1);
		if(it!=S[v[j]].end())
		{
			b=rnk[*it];
			T.insert(rt[dep[j]],rt[dep[j]],1,n,dfn[LCA(b,j)],-1);
		}
		if(it!=S[v[j]].begin())
		{
			--it;
			a=rnk[*it];
			T.insert(rt[dep[j]],rt[dep[j]],1,n,dfn[LCA(a,j)],-1);
		}
		if(a && b)
			T.insert(rt[dep[j]],rt[dep[j]],1,n,dfn[LCA(a,b)],1);
		S[v[j]].insert(dfn[j]);
	}
	while(m--)
	{
		int x=read()^lastans;
		int d=read()^lastans;
		lastans=T.query(rt[min(dep[x]+d,dep[pd[n]])],1,n,dfn[x],dfn[x]+siz[x]-1);
		lastans-=T.query(rt[dep[x]-1],1,n,dfn[x],dfn[x]+siz[x]-1);
		printf("%d\n",lastans);
	}
}
int main()
{
	Log[1]=0;
	for(int i=2;i<MAXN;++i)
		Log[i]=Log[i>>1]+1;
	int Testcases=read();
	while(Testcases--)
	{
		init();
		solve();
	}
	return 0;
}