括号序分块

略。

王室联邦分块

Luogu P2325 SCOI2005 王室联邦

sizbl\text{sizbl} 为一预定好的值，分得的块的大小范围 [sizbl,3sizbl)[\text{sizbl},3\text{sizbl})，且 ≥2sizbl\ge 2\text{sizbl} 的块最多只有一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int sizbl = 100, cntbl, root[MAXn + 10];
int inbl[MAXn + 10];
int top, stk[MAXn + 10];
void EvaBl(int cur, int f) {
    int bottom = top;
    for (int i = head[cur]; i; i = nex[i]) {
        if (to[i] == f) continue;
        EvaBl(to[i], cur);
        if (top - bottom >= sizbl) {
            root[++cntbl] = cur;
            while (top > bottom) {
                inbl[stk[top--]] = cntbl;
            }
        }
    }
    stk[++top] = cur;
}

signed main() {
    // ...
    EvaBl(1, 0);
    if (cntbl == 0) root[++cntbl] = 1;
    while (top) inbl[stk[top--]] = cntbl;
}

树上撒点

按深度从大往小遍历每个点，如果其 0∼sizbl0\sim\text{sizbl} 级祖先中没有关键点，则将其 sizbl\text{sizbl} 级祖先作为关键点。

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
int cntkey, idxkey[MAXn + 10];
int top[MAXn + 10];
bitset<MAXn + 10> info[MAXsqrtn + 10];
int tpstk, stk[MAXn + 10];
void PutKey(int root) {
    while (!pq.empty()) {
        pair<int, int> pr = pq.top(); pq.pop();
        int cur = pr.second;
        for (int i = 0; i <= sizbl && cur && idxkey[cur] == 0; ++i, cur = fa[cur]);
        if (idxkey[cur] == 0) {
            idxkey[cur] = ++cntkey;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (i == root) continue;
        pq.push(make_pair(dep[i], i));
    }
    while (!pq.empty()) {
        pair<int, int> pr = pq.top(); pq.pop();
        int cur = pr.second;
        if (top[cur]) continue;
        if (idxkey[cur]) {
            info[idxkey[pr.second]].set(a[cur], 1);
            stk[++tpstk] = cur;
            for (cur = fa[cur]; cur && idxkey[cur] == 0; cur = fa[cur]) {
                info[idxkey[pr.second]].set(a[cur], 1);
                stk[++tpstk] = cur;
            }
            while (tpstk) {
                top[stk[tpstk--]] = cur;
            }
        } else {
            stk[++tpstk] = cur;
            for (cur = fa[cur]; cur && idxkey[cur] == 0; cur = fa[cur]) {
                stk[++tpstk] = cur;
            }
            while (tpstk) {
                top[stk[tpstk--]] = cur;
            }
        }
    }
}
int Query(int x, int y) {
    bitset<MAXn + 10> ans;
    while (top[x] != top[y]) {
        if (dep[top[x]] > dep[top[y]]) swap(x, y);
        if (idxkey[y]) {
            ans = ans | info[idxkey[y]];
            y = top[y];
        } else {
            ans.set(a[y], 1);
            y = fa[y];
        }
    }
    while (x != y) {
        if (dep[x] > dep[y]) swap(x, y);
        ans.set(a[y], 1);
        y = fa[y];
    }
    ans.set(a[x], 1);
    return ans.count();
}