题意：给出一棵 个节点的树，每个点有一个颜色，颜色为
到 的整数。再给出权值数组 。
有 次查询，每次查询树上只保留
内的所有节点，设一个极大连通块中出现奇数次数的颜色个数为 ，则其对答案的贡献为 ，即答案是所有连通块贡献的和，询问间互相独立。
允许离线，，，时限 ，空限 。
使用回滚莫队。
注意到权值数组是不规则的，只能采取较为暴力的做法。
bitset!
每个点的复杂度权重为其度数，按权重将序列分块。
用 bitset 维护颜色出现次数 的结果。这样支持
合并两个联通块，并查询出现了奇数次的颜色数。
回滚莫队将问题转化为 次联通块合并。复杂度 ，显然无法通过。
还有个问题， 个 bitset
的空间高达 ，也无法承受。
线段树合并！
我们发现，回滚莫队的右指针单调向右移动，此处发生的合并可以用线段树合并维护（还有并查集），于是一趟从左到右的合并被优化到了
。
处理左指针时，可以沿用线段树合并，保留副本， 两次即可撤销贡献。
左指针的复杂度是暴力吗？
考虑“向集合 中插入点
”的复杂度，由于图是一棵树，这肯定小于“向 中插入点 ”的复杂度。
于是，将 的复杂度权重加上“向
中插入点
的复杂度”，不难发现，这个权重的总和等价于从后往前的一次合并，是 的。
按照这个权重来分块，即可做到 。
这个复杂度看起来很对劲，但由于线段树合并的常数较大，难以通过。
启发式合并！位运算魔改线段树！
把线段树合并换成启发式合并，复杂度同样是正确的。注意到按秩合并并查集也是启发式合并，这样实现会很方便。
但我们似乎并没有合适的数据结构。std::set 的启发式合并是
的，
的理论复杂度正确，但常数实在太大。
注意到
较小，可以设计一种特殊的基于位运算的数据结构：
这个数据结构有三层，是一个树形结构。
底层是若干 uint，用于保存颜色出现次数的奇偶性。
第二层每个节点分为 叉，用一个
uint 记录每个分支中是否有值。
将二三层绑定在一起，不动态开点，这样第二层就不需要记录儿子指针，可以直接
调用任意一个儿子。
第一层分为 10 叉，同样用一个 uint
记录每个分支中是否有值。
不同于第二层的是，为了节省空间，此处需要记录儿子指针。
能够发现，单元素集合占用的空间是“一个第二层节点与其子树”，是 个 uint
。而树根占用的空间是
个指针。这样就可以卡进空间限制。
将集合 合并到 时，逐层考虑：
下面给出这个数据结构的实现：
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
| const uint Bas = 4294967295u;
struct BitBlo {
int cnt;
uint rt, buf[32];
void clear() {
while(rt) {
int p = __builtin_ctz(rt);
rt ^= (1u<<p);
buf[p] = 0;
}
cnt = 0;
}
void build(int x) {
rt = (1u<<(x>>5));
buf[x>>5] = (1u<<(x&31));
cnt = 1;
}
}T[MaxN];
int tot;
void Sxor(BitBlo &A, const BitBlo &B) {
uint rt = A.rt&B.rt,
rt2 = (Bas^A.rt)&B.rt;
while(rt) {
int p = __builtin_ctz(rt);
rt ^= (1u<<p);
A.cnt -= __builtin_popcount(A.buf[p]);
A.cnt += __builtin_popcount(A.buf[p]^=B.buf[p]);
if (!A.buf[p]) A.rt ^= (1u<<p);
}
while(rt2) {
int p = __builtin_ctz(rt2);
rt2 ^= (1u<<p);
A.cnt += __builtin_popcount(A.buf[p]=B.buf[p]);
A.rt |= (1u<<p);
}
}
struct Bitset{
uint rt;
int t[10], cnt;
void clear() {
while(rt) {
int p = __builtin_ctz(rt);
rt ^= (1u<<p);
t[p] = 0;
}
cnt = 0;
}
inline void build(int x) {
T[t[x>>10]=++tot].build(x&1023);
rt = (1u<<(x>>10));
cnt = 1;
}
}S[MaxN];
void Sxor(Bitset &A, const Bitset &B) {
uint rt = A.rt&B.rt,
rt2 = (Bas^A.rt)&B.rt;
while(rt) {
int p = __builtin_ctz(rt);
rt ^= (1u<<p);
if (A.t[p]==B.t[p]) {
A.cnt -= T[A.t[p]].cnt;
A.t[p] = 0;
A.rt ^= (1u<<p);
} else {
A.cnt -= T[A.t[p]].cnt;
Sxor(T[A.t[p]], T[B.t[p]]);
A.cnt += T[A.t[p]].cnt;
}
}
while(rt2) {
int p = __builtin_ctz(rt2);
rt2 ^= (1u<<p);
A.cnt += T[A.t[p]=B.t[p]].cnt;
A.rt |= (1u<<p);
}
}
|