给一棵树，每个节点有权值，有若干询问，每次询问某个节点的子树中出现次数大于y的权值x的个数

dfs序上裸莫队可以O(nsqrtn)，平衡树启发式合并O(nlog²n)，线段树合并O(nlogn)，这种类似启发式合并的做法也是O(nlogn)的

sy2006的代码：

#include <cstdio>
#include <algorithm>
#define NE(x, y) ++ne, e[ne]=y, h[ne]=s[x], s[x]=ne
using namespace std;

inline void R(int &x) {
	char ch = getchar(); x = 0;
	for (; ch<'0'; ch = getchar());
	for (; ch>='0'; ch=getchar()) x = x*10 + ch-'0';
}
const int N = 100005;
struct query {
	int k, ans;
} q[N];
int n, m, ne = 0, vt = 0,
	col[N], l[N], st[N], ed[N], sz[N], cnt[N], sum[N],
	s[N], e[N*2], h[N*2], sq[N], hq[N];
void size(int x, int f) {
	sz[x] = 1;
	for (int w=s[x]; w; w=h[w]) if (e[w]!=f)
		size(e[w], x), sz[x] += sz[e[w]];
}
inline void ins(int x) {
	for (int i=st[x]; i<=ed[x]; ++i)
		++sum[++cnt[l[i]]];
}
inline void del(int x) {
	for (int i=st[x]; i<=ed[x]; ++i)
		--sum[cnt[l[i]]--];
}
void solve(int x, int f) {
	st[x] = ++vt; l[vt] = col[x];
	int mx = 0, mf = 0;
	for (int w=s[x]; w; w=h[w]) if (e[w]!=f)
		if (sz[e[w]] > mx)
			mx = sz[e[w]], mf = e[w];
	for (int w=s[x]; w; w=h[w]) if (e[w]!=f && e[w]!=mf)
		solve(e[w], x), del(e[w]);
	if (mx) solve(mf, x);
	for (int w=s[x]; w; w=h[w]) if (e[w]!=f && e[w]!=mf)
		ins(e[w]);
	++sum[++cnt[col[x]]];
	for (int w=sq[x]; w; w=hq[w])
		q[w].ans = sum[q[w].k];
	ed[x] = vt;
}
int main() {
	R(n); R(m);
	for (int i=1; i<=n; ++i) R(col[i]);
	int x, y;
	for (int i=1; i<n; ++i) {
		R(x); R(y);
		NE(x, y); NE(y, x);
	}
	for (int i=1; i<=m; ++i) {
		R(x); R(q[i].k);
		hq[i] = sq[x], sq[x] = i;
	}
	size(1, 0);
	solve(1, 0);
	for (int i=1; i<=m; ++i)
		printf("%d\n", q[i].ans);
	return 0;
}

基本框架十分清晰

考虑每个点被删除的次数，某个点被删一次一定是作为一个轻儿子被删，在与重儿子合并之后所在联通块大小至少*2，故每个点至多被删logn次，所以复杂度保证在O(nlogn)

可以用神奇的复杂度做一些很暴力的事情

感觉跟线段树的合并差不多，不过这个的空间复杂度小多了

这种写法要离线，如果用可持续化线段树维护那个全局数组的话就可以搞成在线。。不过这样跟线段树合并相比并没有什么优势