树剖的小技巧

• 链接
• 分析
• 代码

链接

传送门

分析

第一次看这题的时候感觉和原先写的树上的开关问题很相似，至少在uninstall的部分是对某个节点的子树进行改变，但是后来发现还是有点不一样，因为开关问题终究是状态的反转，而这题的意思就是整体全部改变。有一个小技巧可以省去写查询函数，就是在每次操作前后记录sum[1]，做差即可求结果。因为题目要求改变安装状态的软件包数，这样整体考虑的却很合理。还要注意我们的线段树是从1开始，这里的节点编号从0开始，需调整一下。

代码

#include <cctype>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define mid (l + r) / 2

const int N = 1e5 + 10;
int n, tot, cnt;
int head[N], dep[N], par[N], siz[N];
int top[N], son[N], dfn[N];

struct edge{
    int to, nxt;
}e[N];

inline int read(){
    int x = 0; char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48); ch = getchar();}
    return x;
}

int write(int x){
    if (x < 0){putchar('-'); x = -x;}
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

inline void add(int u, int v){
    e[++tot] = {v, head[u]};
    head[u] = tot;
}

void dfs1(int u, int fa){
    siz[u] = 1;
    dep[u] = dep[fa] + 1;
    par[u] = fa;
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++cnt;
    if (son[u]) dfs2(son[u], tp);
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].to;
        if (v != son[u]) dfs2(v, v);
    }
}

int sum[N << 2], tag[N << 2];
void push_up(int i){
    sum[i] = sum[i << 1] + sum[i << 1|1];
}

void push_down(int i, int l, int r){
    if (tag[i] == -1) return;
    sum[i << 1] = (mid - l + 1) * tag[i];
    sum[i << 1|1] = (r - mid) * tag[i];
    tag[i << 1] = tag[i << 1|1] = tag[i];
    tag[i] = -1;
}

void modify_interval(int i, int l, int r, int crtl ,int crtr, int val){
    if (crtl > r || crtr < l) return;
    if (crtl <= l && crtr >= r){
        sum[i] = (r - l + 1) * val;
        tag[i] = val;
        return;
    }

    push_down(i, l, r);
    if (mid >= crtl) modify_interval(i << 1, l, mid, crtl, crtr, val);
    if (mid < crtr) modify_interval(i <<1|1, mid + 1, r, crtl, crtr, val);
    push_up(i);
}

void modify_tree(int u, int v, int val){
    while (top[u] != top[v]){
        if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
        modify_interval(1, 1, n, dfn[top[u]], dfn[u], val);
        u = par[top[u]];
    }

    if (dep[u] > dep[v]) std::swap(u, v);
    modify_interval(1, 1, n, dfn[u], dfn[v], val);
}


int main() {
    n = read();
    memset(head, -1, sizeof head);
    memset(tag, -1, sizeof tag);
    for (int i = 2, fa; i <= n; ++i) {
        fa = read();
        add(fa + 1, i);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    int q = read(), u;
    char opt[10];
    while (q--){
        scanf("%s", opt);
        u = read();
        ++u;
        int t1 = sum[1];
        if (opt[0] == 'i'){
            modify_tree(1, u, 1);
            write(sum[1] - t1); putchar('\n');
        }
        else{
            modify_interval(1, 1, n, dfn[u], dfn[u] + siz[u] - 1, 0);
            write(t1 - sum[1]); putchar('\n');
        }
    }
    return 0;
}