树上莫队 + 根号分治：ABC477G

G - Frequency Query on Tree

我们先复习一下树上莫队。它可以转化树上的路径变成序列的子区间。

考虑欧拉环游序，每个点只有进去和出来的时候被记录，我们令为 In(x) 和 Out(x)。

对于一个区间，如果一个点出现0次或2次，就不在这条路径上。只有恰好出现1次才在路径上。

考虑现在询问树上两个点 u,vu,v

  1. 如果 uu 是 vv 的祖先，我们需要的区间是 [In(u),In(v)]
  2. 否则，令其LCA为 ww，我们的区间是 [Out(u),In(v)]，但我们需要单独加入 ww 这个点，因为它没有被统计。

image-20260928165805150

好，现在回到这题。

我们用完树上莫队后，还剩下一个某种颜色出现数量+1和查询颜色出现次数区间的操作。如果纯用树状数组之类的复杂度会炸。我们要保证插入是 O(1)O(1) 的，但查询可以是 log⁡q\log q 或 q\sqrt q 的。这里提供两种思路：

  1. 分块
  2. 根号分治。全局对颜色预处理，出现次数小于 n\sqrt n 的直接每次暴力扫，出现次数大于 n\sqrt n 的颜色数量不超过 n\sqrt n 个。

时间复杂度 O(qn)O(q\sqrt n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 200010
struct node {
	int l, r, a, b, i, w; 
};
vector<node>Q; 
int n, m, i, j, k, T;
int z[N << 3], dfn[N], q, a[N], b[N], c[N], cnt[N], hub[N], ans[N]; 
int C[N], In[N], Out[N], f[N][22], dep[N]; 
int l, r, B1, B2, top, u, v; 
vector<int>G[N], E; 

int lca(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y); 
	for(int k = 20; k >= 0; --k)
		if(dep[f[x][k]] >= dep[y]) 
			x  = f[x][k]; 
	if(x == y) return x; 
	for(int k = 20; k >= 0; --k)
		if(f[x][k] != f[y][k])
			x = f[x][k], y = f[y][k]; 
	return f[x][0]; 
}

void dfs1(int x, int fa) {
	dep[x] = dep[fa] + 1; 
	z[++top] = x; In[x] = top; f[x][0] = fa; 
	for(int y : G[x]) if(y != fa) {
		dfs1(y, x); 
	}
	z[++top] = x; Out[x] = top; 
}

signed main() {
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	n = read(); q = read(); 
	B1 = sqrt(n); 
	for(i = 1; i <= n; ++i) {
		a[i] = read(); c[a[i]]++; 
	}
	for(i = 1; i <= n; ++i) 
		if(c[i] > B1) b[i] = -1, E.pb(i); 
		else b[i] = 0, hub[0]++; 
	for(i = 1; i <= n; ++i) debug("%d ", c[i]); debug("\n"); 
	for(i = 1; i <= n; ++i) debug("%d ", b[i]); debug("\n"); 
	for(i = 1; i < n; ++i) {
		u = read(); v = read(); 
		G[u].pb(v); G[v].pb(u); 
	}
	dfs1(1, 0); 
	for(k = 1; k <= 20; ++k) 
		for(i = 1; i <= n; ++i) 
			f[i][k] = f[f[i][k - 1]][k - 1]; 
//	for(i = 1; i <= top; ++i) debug("%d ", z[i]); debug("\n"); 
	B2 = sqrt(top); 
	for(i = 1; i <= q; ++i) {
		u = read(); v = read(); int w = lca(u, v), flg = 0; 
		int ax =  read(), bx = read(); 
		if(w == u) l = In[u], r = In[v], flg = 0; 
		else if(w == v) l = In[v], r = In[u], flg = 0; 
		else {
			if(In[u] < In[v]) l = Out[u], r = In[v]; 
			else l = Out[v], r = In[u]; 
			flg = w; 
		}
		Q.pb({l, r, ax, bx, i, flg}); 
	}
	sort(Q.begin(), Q.end(), [] (node x, node y) -> bool {
		if(x.l / B2 == y.l / B2) return x.r < y.r; 
		return x.l < y.l; 
	}); 
	auto add = [] (int x) ->  void {
		if(b[x] == -1) ++cnt[x]; 
		else --hub[b[x]], ++b[x], ++hub[b[x]]; 
//		debug("Add %d [%d]\n", x, b[x]); 
	}; 
	auto del = [] (int x) -> void {
		if(b[x] == -1) --cnt[x]; 
		else --hub[b[x]], --b[x], ++hub[b[x]]; 
//		debug("Del %d [%d]\n", x, b[x]); 
	}; 
	auto modify = [&] (int x, int y) -> void {
		if(C[x] & 1) del(a[x]); 
		C[x] += y; 
		if(C[x] & 1) add(a[x]); 
	}; 
	l = r = 1; modify(z[1], 1); 
	for(auto t : Q) {
		while(r < t.r) ++r, modify(z[r], 1); 
		while(l > t.l) --l, modify(z[l], 1); 
		while(l < t.l) modify(z[l], -1), ++l; 
		while(r > t.r) modify(z[r], -1), --r; 
//		debug("(%d) [%d %d] (%d %d)\n", t.i, t.l, t.r, t.a, t.b); 
//		for(i = t.l; i <= t.r; ++i) debug("%d ", z[i]); debug("\n"); 
//		for(i = 1; i <= n; ++i) debug("%d ", b[i]); debug("\n"); 
//		for(i = 0; i <= B1; ++i) debug("%d ", hub[i]); debug("\n"); 
		if(t.w) add(a[t.w]); 
		for(i = 1; i <= B1; ++i) 
			if(i >= t.a && i <= t.b) ans[t.i] += hub[i]; 
		for(auto i : E) 
			if(cnt[i] >= t.a && cnt[i] <= t.b) ans[t.i]++; 
		if(t.w) del(a[t.w]); 
	}
	for(i = 1; i <= q; ++i) printf("%d\n", ans[i]); 
	return 0;
}