Frequency Queries(dfs/离线查询/树状数组/数据结构)

题目 题意：给定一棵树，q次查询，每次查询含v，k，l。

• 首先，获取从v到根节点的序列
• 记录序列上每个点的出现次数，移走出现次数小于l次的数
• 给剩下的数去重，并按它们的出现次数，从小到大排序
• 取出第k个数

注意，由于相同次数的数可能有多个，所以答案不唯一。

思路：

• 离线查询。
• dfs遍历树，维护当前序列。并求计算与当前数 u u u相关的所有查询。
• 维护当前序列，每个数的出现次数（用一个计数数组即可）。
• 维护每个出现次数下的元素
• 维护每个出现次数下的元素数量

维护每个出现次数下的元素，可以考虑用set数组，当数 x x x出现次数 n u m num num加一时， s t [ n u m ] . e r a s e ( x ) , s t [ n u m + 1 ] . i n s e r t ( x ) st[num].erase(x),st[num+1].insert(x) st[num].erase(x),st[num+1].insert(x)。

对于当前序列，需要从次数大于等于l的数中，找出出现第k大的，则可以用树状数组，维护出现次数对应的元素数量 c o u n t count count（初始时每个数的出现次数都为0，即 c o u n t 0 = N , c o u n t i = 0 , i > = 1 count_0=N,count_i=0,i>=1 count0​=N,counti​=0,i>=1），用 p r e pre pre为前缀和，对应的个数。我们可以二分找出出现次数最小下标res，使得前缀和 p r e r e s − p r e l − 1 > = k pre_{res}-pre_{l-1}>=k preres​−prel−1​>=k，再取出现次数为 r e s res res的任意数，即为当前查询的答案。 代码翻和改自mrsrz大佬 PS：今天冬至，冬至快乐呀^_^

#include
using namespace std;
const int N=1048579;
int T,n,m,head[N],cnt,a[N],ct[N],fa[N],ans[N],B[N];
// 树状数组，单点更新 
inline void add(int i,int x){for(++i;iT;T--;){
		cin>>n>>m;
		cnt=0;
		for(int i=1;ia[i];
		for(int i=2;i>fa[i];
			e[++cnt]=(edge){i,head[fa[i]]},head[fa[i]]=cnt;
		}
		for(int i=1;i>v>>l>>k;
			vc[v].emplace_back((que){l,k,i});
		}
		dfs(1);
		for(int i=1;i