感觉代码比其他题解更简洁qwq
树链剖分模板题
install x：将1x）
uninstall x：将x子树节点全部变成0（卸载x后x子树节点都会被卸载）
#include <cstdio>
#include <iostream>
#include <cmath>
#include<cstring>
using namespace std;
#define N 200005
inline int in() {
char ch = getchar();
int x = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return x;
}
char st[15];
int n, m, cnt, h[N], w[N], a[N << 2], laz[N << 2];
int f[N], son[N], d[N], top[N], seg[N], s[N];
struct edge {
int v, h;
} e[N << 1];
inline void add(int u, int v) { e[++cnt] = (edge){ v, h[u] }, h[u] = cnt; }
void dfs1(int u, int fa) {
f[u] = fa, d[u] = d[fa] + 1, s[u] = 1; //s：size 子树大小
for (int i = h[u], v; i; i = e[i].h)
if ((v = e[i].v) ^ fa) {
dfs1(v, u), s[u] += s[v];
if (s[v] > s[son[u]])
son[u] = v; //son：重儿子
}
}
void dfs2(int u, int TOP) {
seg[u] = ++cnt, top[u] = TOP;
if (!son[u])
return;
dfs2(son[u], TOP);
for (int i = h[u], v; i; i = e[i].h)
if ((v = e[i].v) ^ son[u] && v ^ f[u])
dfs2(v, v);
}
inline void pushdown(int o, int len) {
laz[o << 1] = laz[o], laz[o << 1 | 1] = laz[o];
a[o << 1] = laz[o] * (len - (len >> 1)), a[o << 1 | 1] = laz[o] * (len >> 1); //实际上就是把“+=”改为“=”
laz[o] = -1;
}
void treeupd(int o, int l, int r, int L, int R, int k) { //k=1表安装，k=0表卸载，这样一来方便更新a数组
if (r < L || l > R)
return;
if (L <= l && R >= r) {
laz[o] = k;
a[o] = k * (r - l + 1); //a就相当于sum
return;
}
if (laz[o] != -1)
pushdown(o, r - l + 1);
int mid = (l + r) >> 1;
treeupd(o << 1, l, mid, L, R, k);
treeupd(o << 1 | 1, mid + 1, r, L, R, k);
a[o] = a[o << 1] + a[o << 1 | 1];
}
inline void upd(int u, int v) {
while (top[u] ^ top[v]) {
if (d[top[u]] < d[top[v]])
swap(u, v);
treeupd(1, 1, n, seg[top[u]], seg[u], 1);
u = f[top[u]];
}
if (d[u] > d[v])
swap(u, v);
treeupd(1, 1, n, seg[u], seg[v], 1);
}
int main() {
scanf("%d", &n);
memset(laz,-1,sizeof(laz));
for (int i = 2, x; i <= n; i++) x = in() + 1, add(x, i); //节点编号统一加1，由于i依赖x，所以建单向边即可
dfs1(1, 1), cnt = 0, dfs2(1, 1);
scanf("%d", &m);
for (int k, x, num; m; m--) {
scanf("%s", st), x = in() + 1, num = a[1]; //num存原已安装节点数
if (st[0] == 'i')
upd(1, x), printf("%d\n", a[1] - num); //upd：修改1~x路径上的节点
else
treeupd(1, 1, n, seg[x], seg[x] + s[x] - 1, 0), printf("%d\n", num - a[1]); //修改x子树
}
}