Description

题库链接

给你 \(n\) 个节点，让你兹磁以下操作，维护一棵树：

1. 动态加边；
2. 修改点权；
3. 询问路径上点权和。

\(1\leq n\leq 30000\)

Solution

好久不打 \(lct\) 了，水一发。 \(lct\) 板子题。

好像 \(lct\) 的题都是板子。

我也不知道我怎么找到这么多板子题的...

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 30000;

int n, m, u, v; char ch[20];

struct Link_Cut_Tree {

    int ch[N+5][2], val[N+5], sum[N+5], pre[N+5], rev[N+5], isrt[N+5];

    Link_Cut_Tree () {for (int i = 1; i <= N; i++) isrt[i] = 1; }

    void pushdown(int o) {

    if (rev[o] == 0) return; int ls = ch[o][0], rs = ch[o][1];

    swap(ch[ls][0], ch[ls][1]), swap(ch[rs][0], ch[rs][1]);

    rev[ls] ^= 1, rev[rs] ^= 1, rev[o] = 0;

    }

    void pushup(int o) {sum[o] = sum[ch[o][0]]+sum[ch[o][1]]+val[o]; }

    void push(int o) {if (isrt[o] == 0) push(pre[o]); pushdown(o); }

    void rotate(int o, int kind) {

    int p = pre[o];

    ch[p][!kind] = ch[o][kind], pre[ch[o][kind]] = p;

    if (isrt[p]) isrt[p] = 0, isrt[o] = 1; else ch[pre[p]][ch[pre[p]][1] == p] = o;

    pre[o] = pre[p];

    ch[o][kind] = p, pre[p] = o;

    pushup(p), pushup(o);

    }

    void splay(int o) {

    push(o);

    while (isrt[o] == 0) {

        if (isrt[pre[o]]) rotate(o, ch[pre[o]][0] == o);

        else {

        int p = pre[o], kind = ch[pre[p]][0] == p;

        if (ch[p][kind] == o) rotate(o, !kind), rotate(o, kind);

        else rotate(p, kind), rotate(o, kind);

        }

    }

    }

    void access(int o) {

    int y = 0;

    while (o) {

        splay(o);

        isrt[ch[o][1]] = 1, isrt[ch[o][1] = y] = 0;

        pushup(o), o = pre[y = o];

    }

    }

    void makeroot(int o) {access(o); splay(o); rev[o] ^=1, swap(ch[o][0], ch[o][1]); }

    void split(int x, int y) {makeroot(x); access(y); splay(y); }

    void link(int x, int y) {makeroot(x); pre[x] = y; }

    void cut(int x, int y) {split(x, y); ch[y][0] = pre[x] = 0, isrt[x] = 1; pushup(y); }

    void update(int x, int key) {makeroot(x); val[x] = key; pushup(x); }

    int query(int x, int y) {split(x, y); return sum[y]; }

    int find(int x) {access(x), splay(x); while (ch[x][0]) x = ch[x][0]; return x; }

}T;

void work() {

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) scanf("%d", &T.val[i]);

    scanf("%d", &m);

    while (m--) {

    scanf("%s%d%d", ch, &u, &v);

    if (ch[0] == 'b') {

        if (T.find(u)^T.find(v)) {puts("yes"); T.link(u, v); }

        else puts("no");

    }else if (ch[0] == 'p') T.update(u, v);

    else {

        if (T.find(u)^T.find(v)) puts("impossible");

        else printf("%d\n", T.query(u, v));

    }

    }

}

int main() {work(); return 0; }