这题是 \(LCT\) 维护子树信息中的 \(LCT\) 维护重心

Description

link

题意概述：给定一个森林，要求支持以下操作

1.链接两个点

2.求一个点所在树的重心

3.求所有重心编号的异或和

Solution

\[Begin
\]

看到有链接和询问操作的题目，我们想到了\(LCT\)

首先是一些重心的性质，本题可以用到：

\(1.\) 点到树上所有点的距离和最小的那个点就是中心

\(2.\) 重心在添加一条边之后只会移动最多一条边的距离

\(3.\) 如果我们联通森林里的两棵树，那么新树的重心就在原两树重心的路径上

应该都由重心的定义理解啥的易证吧\(2333\)

然后我们在处理 \(2\) 操作的时候搞个并查集（\(findroot\)好像很慢）

处理 \(3\) 操作的时候直接在链上进行类似二分查找的东西，看两侧子树的大小关系

\[Q.A.D
\]

\(P.s.\)博主知道应该是\(QED\)

Code

#include <bits/stdc++.h>

using namespace std;

#define int long long

namespace yspm {

inline int read() {

    int res = 0, f = 1;

    char k;

    while (!isdigit(k = getchar()))

        if (k == '-')

            f = -1;

    while (isdigit(k)) res = res * 10 + k - '0', k = getchar();

    return res * f;

}

const int N = 3e5 + 10, inf = 1e15 + 10;

int f[N], c[N][2], s[N], st[N], si[N], n, m, fa[N];

bool r[N];

inline void push_up(int x) { return s[x] = s[c[x][1]] + s[c[x][0]] + si[x] + 1, void(); }

inline bool notroot(int x) { return c[f[x]][0] == x || c[f[x]][1] == x; }

inline void push_down(int x) {

    if (r[x]) {

        swap(c[x][0], c[x][1]);

        r[c[x][0]] ^= 1;

        r[c[x][1]] ^= 1;

    }

    return r[x] = 0, void();

}

inline void push_all(int x) {

    if (notroot(x))

        push_all(f[x]);

    push_down(x);

    return;

}

inline void rotate(int x) {

    int y = f[x], z = f[y], k = (c[y][1] == x), w = c[x][!k];

    if (notroot(y))

        c[z][c[z][1] == y] = x;

    c[x][!k] = y;

    c[y][k] = w;

    if (w)

        f[w] = y;

    f[y] = x;

    f[x] = z;

    return push_up(y);

}

inline void splay(int x) {

    push_all(x);

    while (notroot(x)) {

        int y = f[x], z = f[y];

        if (notroot(y))

            rotate((c[y][0] == x) ^ (c[z][0] == y) ? x : y);

        rotate(x);

    }

    return push_up(x);

}

inline void access(int x) {

    for (int y = 0; x; x = f[y = x]) {

        splay(x);

        si[x] += s[c[x][1]], si[x] -= s[c[x][1] = y];

        push_up(x);

    }

    return;

}

inline void makeroot(int x) {

    access(x);

    splay(x);

    r[x] ^= 1;

    return;

}

inline void split(int x, int y) {

    makeroot(x);

    access(y);

    splay(y);

    return;

}

inline void link(int x, int y) {

    split(x, y);

    si[f[x] = y] += s[x];

    push_up(y);

    return;

}

inline int get(int x) { return fa[x] == x ? x : fa[x] = get(fa[x]); }

inline int update(int x) {

    int l, r, ji = s[x] & 1, sum = s[x] >> 1, lsum = 0, rsum = 0, newp = inf, nl, nr;

    while (x) {

        push_down(x);

        nl = s[l = c[x][0]] + lsum;

        nr = s[r = c[x][1]] + rsum;

        if (nl <= sum && nr <= sum) {

            if (ji) {

                newp = x;

                break;

            } else if (newp > x)

                newp = x;

        }

        if (nl < nr)

            lsum += s[l] + si[x] + 1, x = r;

        else

            rsum += s[r] + si[x] + 1, x = l;

    }

    return splay(newp), newp;

}

signed main() {

    int n = read(), m = read(), x, y, z, ans = 0;

    for (int i = 1; i <= n; ++i) s[i] = 1, fa[i] = i, ans ^= i;

    while (m--) {

        string s;

        cin >> s;

        if (s == "A") {

            x = read();

            y = read();

            link(x, y);

            split(x = get(x), y = get(y));

            z = update(y);

            ans = ans ^ x ^ y ^ z;

            fa[x] = fa[y] = fa[z] = z;

        } else if (s == "Xor")

            printf("%lld\n", ans);

        else

            printf("%lld\n", get(read()));

    }

    return 0;

}

}  // namespace yspm

signed main() { return yspm::main(); }

巴特西

LGOJ4299 首都

Description

Solution

Code

最新文章

热门文章