洛谷P2146 [NOI2015]软件包管理器 题解

发表于 | 分类于

题意：
给定n个软件的依赖关系（除软件0不依赖任何软件，每个软件只依赖一个软件；无环），求每次安装或卸载一个软件会改变多少软件的安装状态。

首先这$n$个软件的依赖关系是一棵树。

我们可以设软件0为根，其他软件依赖哪个软件哪个软件就是这个软件的父节点。

增加一个软件就是把这个软件到根节点的路径上的软件全部安装。

卸载一个软件就是把以这个软件为根节点的字数中的软件全部卸载。

更改软件的个数直接在操作前求一下就行了。

所以这题最终就是 子树/路径 的 修改/查询，树链剖分板子题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <bits/stdc++.h>

using namespace std;

struct edge {
	int t, nxt;
} e[200010];

int n, m, head[100010], cnt, fa[100010];

inline void add_edge(int s, int t) {
	cnt++;
	e[cnt].t = t;
	e[cnt].nxt = head[s];
	head[s] = cnt;
}

inline bool is_digit(char c) {
	return c <= '9' && c >= '0';
}

inline int read() {
	int tmp = 0;
	char c = getchar();
	while(!is_digit(c)) c = getchar();
	while(is_digit(c)) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48), c = getchar();
	return tmp;
}

void write(int x) {
	if(x > 9) write(x / 10);
	putchar((x % 10) ^ 48);
}

inline bool is_alpha(char c) {
	return c >= 'a' && c <= 'z'; 
}

int SegTree[400010], lazy[400010], dfn[100010], size[100010], dfs_cnt, top[100010], sz[400010], depth[100010];

void dfs1(int x) {
	size[x] = 1;
	depth[x] = depth[fa[x]] + 1;
	for(register int i = head[x]; i ; i = e[i].nxt) {
		if(e[i].t == fa[x]) continue ;
		dfs1(e[i].t);
		size[x] += size[e[i].t];
	}
}

void dfs2(int x, int tp) {
	dfn[x] = ++dfs_cnt;
	int maxs = 0;
	top[x] = tp;
	for(register int i = head[x]; i ; i = e[i].nxt) {
		if(e[i].t == fa[x]) continue ;
		if(!maxs) maxs = e[i].t;
		else if(size[maxs] < size[e[i].t]) maxs = e[i].t;
	}
	if(!maxs) return ;
	dfs2(maxs, tp);
	for(register int i = head[x]; i ; i = e[i].nxt) {
		if(e[i].t == fa[x]) continue ;
		if(e[i].t == maxs) continue ;
		dfs2(e[i].t, e[i].t);
	}
}

inline int lson(int x) {
	return x << 1;
}

inline int rson(int x) {
	return x << 1 | 1;
}

inline void pushup(int x) {
	SegTree[x] = SegTree[lson(x)] + SegTree[rson(x)];
}

inline void build(int l, int r, int p) {
	if(l > r) return ;
	lazy[p] = -1;
	sz[p] = r - l + 1;
	if(l == r) return ;
	int mid = (l + r) >> 1;
	build(l, mid, lson(p));
	build(mid + 1, r, rson(p));
}

inline void pushdown(int x) {
	if(lazy[x] == -1) return ;
	if(lazy[x]) SegTree[lson(x)] = sz[lson(x)], SegTree[rson(x)] = sz[rson(x)];
	else SegTree[lson(x)] = SegTree[rson(x)] = 0;
	lazy[lson(x)] = lazy[x];
	lazy[rson(x)] = lazy[x];
	lazy[x] = -1;
}

void modify(int ml, int mr, int l, int r, int p, int opt) {
	if(l > r) return ;
	if(l > mr || r < ml) return ;
	if(ml <= l && r <= mr) {
		if(opt) SegTree[p] = sz[p];
		else SegTree[p] = 0;
		lazy[p] = opt;
		return ;
	}
	pushdown(p);
	int mid = (l + r) >> 1;
	modify(ml, mr, l, mid, lson(p), opt);
	modify(ml, mr, mid + 1, r, rson(p), opt);
	pushup(p);
}

int query(int ql, int qr, int l, int r, int p) {
	if(l > r) return 0;
	if(l > qr || r < ql) return 0;
	if(ql <= l && r <= qr) return SegTree[p];
	pushdown(p);
	int mid = (l + r) >> 1;
	return query(ql, qr, l, mid, lson(p)) + query(ql, qr, mid + 1, r, rson(p));
}

int qtree(int x) {
	return query(dfn[x], dfn[x] + size[x] - 1, 1, n, 1);
}

int qpath(int x) {
	int res = 0;
	while(x) {
		res += query(dfn[top[x]], dfn[x], 1, n, 1);
		x = fa[top[x]];
	}
	return res;
}

void mtree(int x) {
	modify(dfn[x], dfn[x] + size[x] - 1, 1, n, 1, 0);
}

void mpath(int x) {
	while(x) {
		modify(dfn[top[x]], dfn[x], 1, n, 1, 1);
		x = fa[top[x]];
	}
}

int main() {
	n = read();
	for(register int i = 2; i <= n; i++) {
		fa[i] = read() + 1;
		add_edge(fa[i], i);
		add_edge(i, fa[i]);
	}
	build(1, n, 1); 
	dfs1(1);
	dfs2(1, 1);
	m = read();
	while(m--) {
		char c = getchar();
		while(!is_alpha(c)) c = getchar();
		int x = read() + 1;
		if(c == 'i') {
			write(depth[x] - qpath(x)), putchar(10);
			mpath(x);
		} else {
			write(qtree(x)), putchar(10);
			mtree(x);
		}
	}
	return 0;
}