CF570D

我也不知道为什么要写dfn+可持久化数组 （可能刚开始题目理解成到当前子树根节点的深度了）

MLE了第48个点

求大佬尝试帮忙压一下空间

顺便求统计的是在当前子树深度的题

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,m,dfn[500005],size[500005],c[500005],num,root[500005],now,mid,qu,dep,r1,r2,ff,cc1,cc2;
vector<int> G[500005];
char s;
int p;
struct sd
{
	int lson,rson,sum,l,r;
}tree[N*24];
void build(int deep,int x,int cc)
{
	now++;
	tree[now]=tree[x];
	if(tree[now].l==tree[now].r)
	{
		tree[now].sum=(tree[now].sum^(1<<cc));
		return ;
	}
	mid=(tree[now].l+tree[now].r)/2;
	if(deep<=mid)
	{
		tree[now].lson=now+1;
		build(deep,tree[x].lson,cc);
	}
	else
	{
		tree[now].rson=now+1;
		build(deep,tree[x].rson,cc);
	}
	return ;
}
void dfs1(int x,int deep)
{
	size[x]=1;
	num++;
	deep++;
	dfn[x]=num;
	root[num]=now+1;
	build(deep,root[num-1],c[x]);
	for(int i=0;i<G[x].size();i++)
	{
		dfs1(G[x][i],deep);
		size[x]+=size[G[x][i]];
	}
	return ;
}

void make(int ll,int rr)
{
	now++;
	tree[now].l=ll;
	tree[now].r=rr;
	if(ll==rr) return ;
	else
	{
		int id=now;
		tree[id].lson=now+1;
		make(ll,(ll+rr)/2);
		tree[id].rson=now+1;
		make((ll+rr)/2+1,rr);
	}
}
void work(int dep,int x1,int x2)
{
	if(tree[x1].l==tree[x1].r)
	{
		ff=0;
		for(int i=0;i<=25;i++)
		{
			cc1=(int(tree[x2].sum&(1<<i))!=0);
			cc2=(int(tree[x1].sum&(1<<i))!=0);
			if((cc1+cc2)==1) ff++;
		}
		if(ff>=2) printf("No\n");
		else printf("Yes\n");
		return ;
	}
	else
	{
		mid=(tree[x1].l+tree[x1].r)/2;
		if(dep<=mid)
		{
			work(dep,tree[x1].lson,tree[x2].lson);
		}
		else 
		{
			work(dep,tree[x1].rson,tree[x2].rson);
		}
	}
	return ;
}
void query(int x)
{
	if(tree[x].l==tree[x].r)
	{
		cout<<x<<" "<<tree[x].l<<" "<<tree[x].sum<<endl;
		return ;
	}
	else 
	{
		query(tree[x].lson);
		query(tree[x].rson);
	}
}
int main()
{
	cin>>n>>m;
	for(int i=2;i<=n;i++)
	{
		scanf("%d",&p);
		G[p].push_back(i);
	}
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		c[i]=s-'a';
	}
	root[0]=1;
	make(1,n);
	dfs1(1,0);
	//query(root[dfn[3]-1]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&qu,&dep);
		r1=dfn[qu]-1;
		r2=r1+size[qu];
		work(dep,root[r1],root[r2]);
	}
	return 0;
}