SP16549 QTREE6 - Query on a tree VI

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

LCT维护子树大小经典题
多 记 录 一 个 s i [ x ] 表 示 非 实 边 儿 子 的 子 树 大 小 和 多记录一个si[x]表示非实边儿子的子树大小和 多记录一个si[x]表示非实边儿子的子树大小和
维护也很方便,直接看代码吧
注意!!写LCT断边的时候不要直接写连等,这是从右到左赋值的(调了一上午)

没啥细节

code:

#include<bits/stdc++.h>
#define N 100050
#define I inline
using namespace std;
I int read() {
    int x = 0;
    char ch = getchar();
    for(; ch < '0' || ch > '9'; ) ch = getchar();
    for(; ch >= '0' && ch <= '9'; ) x = (x << 3) + (x << 1) + (ch - 48), ch = getchar();
    return x;
}
struct edge {
    int v, nxt;
} e[N << 1];
int p[N], eid, Fa[N];
I void init() {
    memset(p, -1, sizeof p);
    eid = 0;
}
I void insert(int u, int v) {
    e[eid].v = v;
    e[eid].nxt = p[u];
    p[u] = eid ++;
}

#define ls ch[x][0]
#define rs ch[x][1]
struct LCT {
    int fa[N], ch[N][2], s[N], si[N];
    I void init(int n) { for(int i = 1; i <= n + 1; i ++) s[i] = 1; }
    I void update(int x) {
        s[x] = s[ls] + s[rs] + si[x] + 1;
    }
    I int nrt(int x) {
        return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
    }
    I int get(int x) {
        return ch[fa[x]][1] == x;
    }
    I void rotate(int x) {
        int f = fa[x], gf = fa[f], k = get(x);
        if(nrt(f)) ch[gf][get(f)] = x; fa[x] = gf;
        ch[f][k] = ch[x][!k], fa[ch[x][!k]] = f;
        ch[x][!k] = f, fa[f] = x;
        update(f), update(x);
    }
    I void splay(int x) {
        int f = fa[x];
        while(nrt(x)) { //printf("%d %d    %d\n", x, f, fa[1]);
            if(nrt(f)) rotate(get(f) == get(x)? f : x);
            rotate(x);
            f = fa[x];
            if(f == x) exit(1);
        }
    }
    I void access(int x) {
        for(int y = 0; x; y = x, x = fa[x]) {
            splay(x);
            si[x] += s[rs];
            rs = y;
            si[x] -= s[rs];
        }
    }
    I int findroot(int x) {
        access(x), splay(x);
        while(ls) x = ls;
        splay(x); return x;
    }
    I void link(int x) {
        splay(x);
        int y = Fa[x];// printf("      %d %d\n", x, y);
        fa[x] = y;
        access(y), splay(y);
        si[y] += s[x]; s[y] += s[x];
        update(y);
    }
    I void cut(int x) {
        access(x), splay(x);
        fa[ls] = 0;//这里不要写连等!!!!
        ls = 0;
        update(x);
    }
} t[2];
I void dfs(int u) {
    t[0].link(u);
    for(int i = p[u]; i + 1; i = e[i].nxt) {
        int v = e[i].v;
        if(v == Fa[u]) continue;
        Fa[v] = u; dfs(v);
    }
}
int n, m, col[N];
int main() {
    init();
    n = read();
    for(int i = 1; i < n; i ++) {
        int u, v;
        u = read(), v = read();
        insert(u, v), insert(v, u);
    }
    Fa[1] = n + 1;
    t[0].init(n), t[1].init(n);
    dfs(1);
  //  for(int i = 1; i <= n; i ++) t[0].link(i);
    m = read();
    while(m --) {
        int o, x;
        o = read(), x = read();
        if(o == 1) t[col[x]].cut(x), t[col[x] ^= 1].link(x);
        else {
            int rt = t[col[x]].findroot(x);
            printf("%d\n", t[col[x]].s[t[col[x]].ch[rt][1]]);
        }
    }
    return 0;
}
/*
 4
 1 2
 1 3
 3 4
 2
 1 3
 1 3
 */
上一篇:2 window进程


下一篇:Code Style