题目大意：给出一棵树，每个节点代表一个软件包，安装这个软件包要安装他所有祖先，卸载要卸载他的子树，每次操作后问操作了多少个软件包。

【题解】

树链剖分裸题啊。

# include <stdio.h>
using namespace std;

const int N = 200010, M = 600010;
int n;
int tot=0, next[M], to[M], head[N];
int dfn[N], dfnlast[N], DFN = 0, sz[N], top[N], son[N];
int dep[N], pos[N], father[N];
inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dfs(int x, int fa=0) {
	dep[x] = dep[fa] + 1; father[x] = fa; 
	sz[x]=1; son[x]=-1;	
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		dfs(to[i], x);
		sz[x] += sz[to[i]];
		if(son[x] == -1 || sz[to[i]] > sz[son[x]])
			son[x] = to[i];
	}
}

inline void dfs2(int x, int tp, int fa=0) {
	dfn[x]=pos[x]=++DFN; top[x]=tp;
	if(son[x] != -1) dfs2(son[x], tp, x);
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa || to[i] == son[x]) continue;
		dfs2(to[i], to[i], x);
	}
	dfnlast[x] = DFN;
}


int w[N<<2], lazy[N<<2];
 
inline void pushdown(int x, int l, int r) {
    if(lazy[x] == -1) return;
    int mid = l+r >> 1;
    w[x<<1] = lazy[x] * (mid - l + 1);
    w[x<<1|1] = lazy[x] * (r - (mid+1) + 1);
    lazy[x<<1] = lazy[x];
    lazy[x<<1|1] = lazy[x];
    lazy[x] = -1;
}
 
inline void change(int x, int l, int r, int L, int R, int delta) {
    if(L <= l && r <= R) {
        w[x] = delta*(r - l + 1);
        lazy[x] = delta;
        return ;
    }
    pushdown(x, l, r);
    int mid = l+r >> 1;
    if(L > mid) change(x<<1|1, mid+1, r, L, R, delta);
    else if(R <= mid) change(x<<1, l, mid, L, R, delta);
    else {
        change(x<<1, l, mid, L, mid, delta);
        change(x<<1|1, mid+1, r, mid+1, R, delta);
    }
    w[x] = w[x<<1] + w[x<<1|1];
}
 
inline int query(int x, int l, int r, int L, int R) {
    if(L <= l && r <= R) return w[x];
    pushdown(x, l, r);
    int mid = l+r >> 1;
    if(L > mid) return query(x<<1|1, mid+1, r, L, R);
    else if(R <= mid) return query(x<<1, l, mid, L, R);
    else return query(x<<1, l, mid, L, mid) + query(x<<1|1, mid+1, r, mid+1, R);
}

inline int get(int fr, int to) {
	int ret = 0;
	while(top[fr] != top[to]) {
		ret += query(1, 1, n, pos[top[fr]], pos[fr]);
		change(1, 1, n, pos[top[fr]], pos[fr], 1);
		fr = father[top[fr]];
	}
	if(pos[fr] >= pos[to]) {
		ret += query(1, 1, n, pos[to], pos[fr]);
		change(1, 1, n, pos[to], pos[fr], 1);
	}
	return ret;
}

int main() {
	scanf("%d", &n);
	for (int i=2, t; i<=n; ++i) {
		scanf("%d", &t); ++t;
		add(t, i); add(i, t);
	}
	dfs(1); dfs2(1,1);
	int tsz = n<<2;
	for (int i=1; i<=tsz; ++i) lazy[i] = -1;
	int q; scanf("%d", &q);
	while(q--) {
		int x; char str[12];
		scanf("%s%d", str, &x); ++x;
		if(str[0] == 'i') {
			printf("%d\n", dep[x] - get(x, 1));
		} else {
			printf("%d\n", query(1, 1, n, dfn[x], dfnlast[x]));
			change(1, 1, n, dfn[x], dfnlast[x], 0);
		}
	}
	return 0;
}

感觉dfs序也能做？

但是线段树好像要维护一些奇奇怪怪的东西

比如只更新符号为负的，而且好像lazy多了就当一个用？？

奇怪的东西。。感觉不可写弃坑了。