Statement

给你 nn 个点的空白图（即初始时没有边）。请你支持：加边；求 xx 所在连通块重心；求所有连通块重心的异或和。保证任何时刻图是森林。

数据范围：n≤105n\le10^5，m≤2×105m\le2\times10^5。

Solution

树的重心的性质可以看 这里。

Algorithm 1

这个做法需要用到的树的重心的性质：

  1. 一棵树添加一个点，重心最多移动一条边。
  2. 删掉重心后，最大连通块大小小于等于总结点个数的一半。

根据性质 1，合并两棵树时我们启发式合并，暴力地将较小的那棵树中的点一个一个地插入较大的那棵树。

用 LCT 维护子树大小，对每个点维护两个值：所有虚儿子子树大小之和 vir\text{vir}，Splay 上子树内所有点的虚儿子子树大小之和 sum\text{sum}。查询点 xx 的子树大小，可以将它旋转成所在 Splay 的根，然后求 sum(x)+vir(rson(x))+1\text{sum}(x)+\text{vir}(\text{rson}(x))+1。比较重心当然是比较两个点两边连通块最大值。

时间复杂度 O(nlog⁡2n)O(n\log^2n)。

Algorithm 2

这个做法需要用到的树的重心的性质：

  1. 合并两棵树，新的重心在原来两个重心的连线上。
  2. 删掉重心后，最大连通块大小小于等于总结点个数的一半。

把原来两个重心的连线拎出来，然后在这棵 Splay 上二分，找到最大连通块小于等于总结点个数的一半的一个或两个点。

注意到虚子树一定不会是最大的那个连通块，所以只需要维护这条路径上半部分的连通块大小，和下半部分的连通块大小即可。根据这两个连通块的大小关系，再决定向左儿子还是右儿子递归。具体可以看代码实现。

时间复杂度 O(nlog⁡n)O(n\log n)。

Code

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int query(int u, int v) {
    Node *x = pool + u, *y = pool + v;
    makeRoot(y), access(x), splay(x);
    int all = x->sum / 2, lsum = 0, rsum = 0, rt = INT_MAX;
    while (x != null) {
        x->pushdown();
        int lef = lsum + x->son[0]->sum, rig = rsum + x->son[1]->sum;
        if (std::max(lef, rig) <= all) rt = std::min(rt, int(x - pool));
        if (lef < rig)
            lsum += 1 + x->vrt + x->son[0]->sum, x = x->son[1];
        else
            rsum += 1 + x->vrt + x->son[1]->sum, x = x->son[0];
    }
    return rt;
}

完整代码

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
#include <bits/stdc++.h>
namespace IO {
void input(int& x) {
    bool f;
    char c;
    for (f = 0; !isdigit(c = getchar());)
        if (c == '-') f = 1;
    for (x = 0; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ '0');
    if (f) x = -x;
}
void output(int x, char c = '\n') {
    static char f[97];
    int pf = 0;
    if (!x) return putchar('0'), putchar(c), void();
    if (x < 0) x = -x, putchar('-');
    while (x) f[pf++] = x % 10 + '0', x /= 10;
    while (pf) putchar(f[--pf]);
    putchar(c);
}
}  // namespace IO
using namespace IO;
const int N = 1e6 + 7, INF = 1e9;
namespace US {
int dad[N], ans = 0;
void init(int n) {
    for (int i = 1; i <= n; i++) dad[i] = i, ans ^= i;
}
int find(int x) { return x == dad[x] ? x : (dad[x] = find(dad[x])); }
void merge(int c, int x, int y) { dad[c] = dad[x] = dad[y] = c, ans ^= c ^ x ^ y; }
}  // namespace US
namespace LCT {
struct Node* null;
struct Node {
    Node *pre, *son[2];
    int vrt, sum;
    bool rev;
    bool get() const { return pre->son[1] == this; }
    bool isRoot() const { return pre->son[0] != this && pre->son[1] != this; }
    void connect(Node* x, bool id) {
        if (this != null) son[id] = x;
        if (x != null) x->pre = this;
    }
    void pushup() { sum = 1 + vrt + son[0]->sum + son[1]->sum; }
    void pushdown() {
        if (rev) {
            std::swap(son[0], son[1]);
            if (son[0] != null) son[0]->rev ^= 1;
            if (son[1] != null) son[1]->rev ^= 1;
            rev = 0;
        }
    }
    void rotate() {
        Node *y = pre, *z = y->pre;
        bool k = get(), kk = y->get(), t = y->isRoot();
        y->connect(son[k ^ 1], k), connect(y, k ^ 1);
        if (t)
            pre = z;
        else
            z->connect(this, kk);
        y->pushup(), pushup();
    }
} pool[N], *tail;
void splay(Node* x) {
    static Node* stk[N];
    int pstk = 0;
    Node* y = stk[++pstk] = x;
    while (!x->isRoot()) stk[++pstk] = x = x->pre;
    while (pstk) stk[pstk--]->pushdown();
    for (x = y; !x->isRoot(); x->rotate())
        if (!(y = x->pre)->isRoot()) (x->get() == y->get() ? y : x)->rotate();
}
void access(Node* x) {
    for (Node* y = null; x != null; x = (y = x)->pre)
        splay(x), x->vrt += x->son[1]->sum, x->connect(y, 1), x->vrt -= y->sum, x->pushup();
}
void makeRoot(Node* x) { access(x), splay(x), x->rev ^= 1; }
void init(int n) {
    *(null = pool) = {null, {null, null}, 0, 0, 0}, tail = pool + n;
    for (int i = 1; i <= n; i++) *(pool + i) = *null, (pool + i)->sum = 1;
}
void link(int u, int v) {
    Node *x = pool + u, *y = pool + v;
    makeRoot(x), makeRoot(y);
    y->pre = x, x->vrt += y->sum, x->pushup();
}
int query(int u, int v) {
    Node *x = pool + u, *y = pool + v;
    makeRoot(y), access(x), splay(x);
    int all = x->sum / 2, lsum = 0, rsum = 0, rt = INT_MAX;
    while (x != null) {
        x->pushdown();
        int lef = lsum + x->son[0]->sum, rig = rsum + x->son[1]->sum;
        if (std::max(lef, rig) <= all) rt = std::min(rt, int(x - pool));
        if (lef < rig)
            lsum += 1 + x->vrt + x->son[0]->sum, x = x->son[1];
        else
            rsum += 1 + x->vrt + x->son[1]->sum, x = x->son[0];
    }
    return rt;
}
}  // namespace LCT
int n, m;
int main() {
    input(n), input(m), LCT::init(n), US::init(n);
    while (m--) {
        static char str[5];
        int x, y;
        scanf("%s", str);
        if (*str == 'A') {
            input(x), input(y);
            int rtx = US::find(x), rty = US::find(y);
            LCT::link(x, y), US::merge(LCT::query(rtx, rty), rtx, rty);
        } else if (*str == 'Q')
            input(x), output(US::find(x));
        else
            output(US::ans);
    }
    return 0;
}