【题解】CF1585E Frequency Queries

思路 by @houzhiyuan

Sol

感觉在线不怎么可做，考虑离线。
那么问题变成了维护路径上第 \(k\) 大出现次数的数。
考虑线段树，以出现次数为节点的下标，那么查询相当于是求第 \(k\) 大。
线段树二分即可。
存方案的话开个 set 维护一下每个指即可。
时间复杂度 \(O(Q \log n)\)。
具体实现看代码。

Code

//LYC_music yyds!
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0)
#define lowbit(x) (x&(-x))
using namespace std;
inline char gc()
{
	static char buf[1000000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
int read()
{
	int pos=1,num=0;
	char ch=getchar();
	while (!isdigit(ch))
	{
		if (ch=='-') pos=-1;
		ch=getchar();
	}
	while (isdigit(ch))
	{
		num=num*10+(int)(ch-'0');
		ch=getchar();
	}
	return pos*num;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		write(-x);
		return;
	}
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
void writesp(int x)
{
	write(x);
	putchar(' ');
}
void writeln(int x)
{
	write(x);
	putchar('\n');
}
const int N=1e6+10;
struct node
{
	int l,k,id;
};
set<int> s[N];
vector<int> G[N];
vector<node> q[N];
int siz[N<<2],n,m,a[N],cnt[N],ans[N];
void update(int k,int l,int r,int pos,int x1,int x2)
{
	siz[k]+=x2;
	if (l==r)
	{
		if (x2==1) s[l].insert(x1);
		else s[l].erase(x1);
		return;
	}
	int mid=(l+r)>>1;
	if (pos<=mid) update(k<<1,l,mid,pos,x1,x2);
	else update(k<<1|1,mid+1,r,pos,x1,x2);
}
int querysum(int k,int l,int r,int L,int R)
{
	if (L>R) return 0;
	if (L<=l&&r<=R) return siz[k];
	int mid=(l+r)>>1,res=0;
	if (L<=mid) res+=querysum(k<<1,l,mid,L,R);
	if (mid<R) res+=querysum(k<<1|1,mid+1,r,L,R);
	return res;
}
int query(int k,int l,int r,int val)
{
	if (siz[k]<val) return -1;
	if (l==r) return *s[l].begin();
	int mid=(l+r)>>1;
	if (siz[k<<1]>=val) return query(k<<1,l,mid,val);
	else return query(k<<1|1,mid+1,r,val-siz[k<<1]);
}
void dfs(int x,int fa)
{
	if (cnt[a[x]]) update(1,1,n,cnt[a[x]],a[x],-1);
	cnt[a[x]]++;
	update(1,1,n,cnt[a[x]],a[x],1);
	for (auto now:q[x])
		ans[now.id]=query(1,1,n,now.k+(now.l>1)*(querysum(1,1,n,1,now.l-1)));
	for (auto v:G[x])
	{
		if (v==fa) continue;
		dfs(v,x);
	}
	update(1,1,n,cnt[a[x]],a[x],-1);
	cnt[a[x]]--;
	if (cnt[a[x]]) update(1,1,n,cnt[a[x]],a[x],1);
}
void solve()
{
	n=read(); m=read();
	for (int i=1;i<=n;i++)
		a[i]=read(),G[i].clear(),q[i].clear();
	for (int i=2;i<=n;i++)
	{
		int x=read();
		G[x].emplace_back(i); G[i].emplace_back(x);
	}
	for (int i=1;i<=m;i++)
	{
		int x=read(),l=read(),k=read();
		q[x].push_back({l,k,i});
	}
	dfs(1,0);
	for (int i=1;i<=m;i++)
		writesp(ans[i]);
	putchar('\n');
}
signed main()
{
	int T=read();
	while (T--) solve();
}