DDOSvoid's Blog

Luogu P4299 首都

发表于 分类于
本文字数： 3.3k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/P4299

简要题意：给定 $n$ 个点，现在有 $m$ 次操作，操作有三种，第一种操作给定两个点 $x,y$，加入一条连接 $x$ 和 $y$ 的边，保证连边后仍然是森林；第二种操作给定一个点 $x$，求 $x$ 所在连通块的重心，如果有两个重心输出编号较小的那个；第三种操作求所有连通块重心的编号的异或和

$n\le 10^5,m\le 2\times 10^5$

Solution

根据重心的性质，把两棵树通过某一点相连得到一颗新的树，新的树的重心必然在连接原来两棵树重心的路径上，那么我们使用并查集维护每个连通块的重心，每次合并时用 $LCT$ 把两个重心所在的路径拉出来，然后我们在这个路径上二分

这里的二分是在 $Splay$ 上进行的，我们从根节点开始进行，然后我们比较以该节点为整棵树的根时，它的左子树的大小和右子树的大小，然后我们选择较大的进入即可，需要注意在进入子树时需要维护被扔掉的子树的信息

时间复杂度 $O(n\log 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
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define maxn 100010
#define INF 1000000000
using namespace std;

#define lc T[i].ch[0]
#define rc T[i].ch[1]
struct LinkCutTree { 
    int v, sv, val, ch[2];
    bool rev; 
} T[maxn]; int f[maxn];
void init_LCT(int n) {
    for (int i = 1; i <= n; ++i) T[i].v = T[i].val = 1;
}
inline int get(int i) {
    if (T[f[i]].ch[0] == i) return 0;
    if (T[f[i]].ch[1] == i) return 1;
    return -1;
}
inline void maintain(int i) {
    T[i].v = T[i].val + T[i].sv + T[lc].v + T[rc].v;
} 
inline void setr(int i) { 
    if (!i) return ;
    T[i].rev ^= 1; swap(lc, rc); 
}
inline void push(int i) {
    bool &rev = T[i].rev; 
    if (rev) setr(lc), setr(rc);
    rev = 0;
}
inline void rotate(int x) {
    int fa = f[x], ffa = f[f[x]], wx = get(x);
    if (~get(fa)) T[ffa].ch[T[ffa].ch[1] == fa] = x;
    f[x] = ffa; f[fa] = x; f[T[x].ch[wx ^ 1]] = fa;
    T[fa].ch[wx] = T[x].ch[wx ^ 1]; T[x].ch[wx ^ 1] = fa;
    maintain(fa); maintain(x); 
} 
void clt(int i) {
    static int st[maxn], top;
    st[top = 1] = i; 
    while (~get(i)) st[++top] = i = f[i];
    while (top) push(st[top--]); 
}
void Splay(int i) {
    clt(i);
    for (int fa = f[i]; ~get(i); rotate(i), fa = f[i])
        if (~get(fa)) rotate(get(i) == get(fa) ? fa : i);
}
void access(int i) {
    for (int p = 0; i; i = f[p = i]) {
        Splay(i);
        T[i].sv += T[rc].v;
        T[i].sv -= T[p].v;
        rc = p; maintain(i);
    }
}
inline void make_rt(int i) { access(i); Splay(i); setr(i); }
inline void split(int x, int y) { make_rt(x); access(y); Splay(y); }
int find_rt(int i) { access(i); Splay(i); while (lc) i = lc; return Splay(i), i; }
inline void link(int x, int y) { 
    split(x, y); f[x] = y; 
    T[y].sv += T[x].v; maintain(y);
}

int solve(int x, int y) {
    split(x, y); int sum = T[y].v, i = y, lv = 0, rv = 0, res = INF;
    while (i) {
        push(i);
        int L = lv + T[lc].v, R = rv + T[rc].v;
        if (max(L, R) <= sum / 2) res = min(res, i);
        if (L > R) rv += T[rc].v + T[i].sv + T[i].val, i = lc;
        else lv += T[lc].v + T[i].sv + T[i].val, i = rc;
    } return Splay(res), res;
}

int fa[maxn], w[maxn], ans;
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i, w[i] = i, ans ^= w[i]; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    fa[fx] = fy;
    ans ^= w[fx], ans ^= w[fy];
    w[fy] = solve(w[fx], w[fy]), ans ^= w[fy];
}

int n, m;

inline void solve_1() {
    int x, y; cin >> x >> y;
    link(x, y), merge(x, y); 
}

inline void solve_2() {
    int x; cin >> x;
    cout << w[find(x)] << "\n";
}

inline void solve_3() {
    cout << ans << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; init_LCT(n); init_fa(n);
    for (int i = 1; i <= m; ++i) {
        char c[10]; cin >> c;
        switch (c[0]) {
        case 'A': solve_1(); break;
        case 'Q': solve_2(); break;
        case 'X': solve_3(); break;
        }
    }
    return 0;
}