C++ 解法, 执行用时: 3075ms, 内存消耗: 80412K, 提交时间: 2022-05-05 14:56:23

#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
int ne[N*2],e[N*2],h[N],idx;
int dep[N],son[N],sz[N];
int tr[500][N];
struct Node
{
	int y,k,id;
};
int n,q;
vector<Node>Q[N];
int ans[N];
int exis[N],col[N];
int len;
void add(int a,int b)
{
	ne[idx]=h[a],e[idx]=b,h[a]=idx++;
}
int get(int x)
{
	return x/len;
}
void dfn(int u,int fa)
{
	sz[u]=1;
	dep[u]=dep[fa]+1;
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		dfn(j,u);
		sz[u]+=sz[j];
		if(sz[j]>sz[son[u]])son[u]=j;
	}
}
void add(int p[N],int x,int v)
{	
	for(int i=x;i<=n;i+=lowbit(i))
		p[i]+=v;
}
int query(int p[N],int x,int y)
{
	int res=0;
	x--;
	for(int i=x;i;i-=lowbit(i))
    	res-=p[i];
    for(int i=y;i;i-=lowbit(i))
    	res+=p[i];
    return res;
}
void ud(int u)
{	
	if(exis[col[u]]<=dep[u])return;
	if(exis[col[u]]!=INF)add(tr[get(col[u])],exis[col[u]],-1);
	exis[col[u]]=dep[u];
	add(tr[get(col[u])],dep[u],1);
}
void del(int u)
{	
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		del(j);		
	}
	if(exis[col[u]]==INF)return;
	if(exis[col[u]]!=INF)add(tr[get(col[u])],exis[col[u]],-1);
	exis[col[u]]=INF;
}
void gets(int u)
{
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		gets(j);
	}
		ud(u);
	
}
void dfs(int u,int fp)
{
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j!=son[u])dfs(j,0);
	}
	if(son[u])dfs(son[u],1);
	for(int i=h[u];~i;i=ne[i])
	{
		int j=e[i];
		if(j!=son[u])gets(j);
	}
	ud(u);
	for(int i=0;i<Q[u].size();i++)
	{
		int x=dep[u],y=x+Q[u][i].y,k=Q[u][i].k,id=Q[u][i].id;
		y=min(y,n);
		ans[id]=-1;
		for(int j=0;j<len;j++)
		{
			int sum=query(tr[j],x,y);
			if(sum<k)
			{
				k-=sum;
				continue;
			}
			for(int l=j*len;;l++)
				{
					int w=(exis[l]>=x&&exis[l]<=y);
					if(w<k){k-=w;continue;}
					ans[id]=l;break;
				}
			break;
		}
	}
	if(fp)return;del(u);
}
int main()
{
	cin>>n>>q;
	memset(h,-1,sizeof h);
	memset(exis,0x3f,sizeof exis);
	for(int i=2;i<=n;i++)
	{	int x;
		scanf("%d",&x);
		add(x,i);
	}
	len=(int)sqrt(n)+1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&col[i]);
	}
	dep[1]=1;
	dfn(1,0);
	for(int i=1;i<=q;i++)
	{
		int x,y,k;
		scanf("%d%d%d",&x,&y,&k);
		Q[x].push_back({y,k,i});
	}
	dfs(1,1);
	for(int i=1;i<=q;i++)
		cout<<ans[i]<<endl;
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 1811ms, 内存消耗: 197888K, 提交时间: 2019-03-02 20:55:14

#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
const int _=1e5+5,__=4e7+5;
int n,Q,dep[_],siz[_],son[_],ans[_],w[_],G[_],cnt,mx,num=1;
int rt[_<<2],F[_<<2],f[_],g[_],lc[__],rc[__],t[__];
struct ljq{
	int y,k,id;
};
vector<int>e[_];
vector<ljq>q[_];
void dfs(int u){
	siz[u]=1;
	for(int v:e[u]){
		dep[v]=dep[u]+1;
		dfs(v);siz[u]+=siz[v];
		if(siz[son[u]]<siz[v])son[u]=v;
	}
}
void NEW(int &no){
	++cnt;t[cnt]=t[no];
	lc[cnt]=lc[no];	rc[cnt]=rc[no];
	no=cnt;
}
void modify(int &no,int l,int r,int k,int x){
	if(!no)NEW(no);t[no]+=x;
	if(l==r)return;
	if(k<=mid)modify(lc[no],l,mid,k,x);
	else modify(rc[no],mid+1,r,k,x);
}
void update(int no,int l,int r,int k,int x,int opt){
	if(F[no]!=num)F[no]=num,rt[no]=0;
	modify(rt[no],1,n,x,opt);
	if(l==r)return;
	if(k<=mid)update(no<<1,l,mid,k,x,opt);
	else update(no<<1|1,mid+1,r,k,x,opt);
}
int Query(int no,int l,int r,int k){
	if(!no||l==r)return t[no];
	if(k<=mid)return Query(lc[no],l,mid,k);
	else return t[lc[no]]+Query(rc[no],mid+1,r,k);
}
int query(int no,int l,int r,int k,int x){
	if(l==r)return k-(g[l]==num&&f[l]<=x)==0?l:-1;
	if(F[no<<1]!=num)F[no<<1]=num,rt[no<<1]=0;
	int s=Query(rt[no<<1],1,n,x);
	if(s>=k)return query(no<<1,l,mid,k,x);
	else return query(no<<1|1,mid+1,r,k-s,x);
}
void insert(int x,int y){
	if(g[x]!=num)g[x]=num,f[x]=y,update(1,1,n,x,y,1);
	if(y<f[x]){
		update(1,1,n,x,f[x],-1);
		update(1,1,n,x,y,1);
		f[x]=y;
	}
}
void clear(){cnt=0;num++;}
queue<int>qu;
void bfs(int x){
	qu.push(x);
	while(!qu.empty()){
		int u=qu.front();qu.pop();
		insert(w[u],dep[u]);
		for(int v:e[u])qu.push(v);
	}
}
void Dfs(int u){
	for(int v:e[u])if(v!=son[u])Dfs(v),clear();
	if(son[u])Dfs(son[u]); insert(w[u],dep[u]);
	for(int v:e[u])if(v!=son[u])bfs(v);
	for(ljq x:q[u])ans[x.id]=query(1,1,n,x.k,dep[u]+x.y);
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>Q;
	for(int i=2;i<=n;++i){
		int x;cin>>x;
		e[x].push_back(i);
	}
	for(int i=1;i<=n;++i)cin>>w[i],assert(w[i]>=1&&w[i]<=n);
	for(int i=1;i<=Q;++i){
		int x,y,k;cin>>x>>y>>k;
		q[x].push_back((ljq){y,k,i});
	}
	dep[1]=1;dfs(1);Dfs(1);
	for(int i=1;i<=Q;++i)cout<<ans[i]<<endl;
	return 0;
}