【洛谷p2146】NOI2015软件包管理器

题目描述

Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器,你可以通过一行命令安装某一个软件包,然后软件包管理器会帮助你从软件源下载软件包,同时自动解决所有的依赖(即下载安装这个软件包的安装所依赖的其它软件包),完成所有的配置。Debian/Ubuntu使用的apt-get,Fedora/CentOS使用的yum,以及OSX下可用的homebrew都是优秀的软件包管理器。

你决定设计你自己的软件包管理器。不可避免地,你要解决软件包之间的依赖问题。如果软件包A依赖软件包B,那么安装软件包A以前,必须先安装软件包B。同时,如果想要卸载软件包B,则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且,由于你之前的工作,除0号软件包以外,在你的管理器当中的软件包都会依赖一个且仅一个软件包,而0号软件包不依赖任何一个软件包。依赖关系不存在环(若有m(m≥2)个软件包A1,A2,A3,⋯,Am,其中A1依赖A2,A2依赖A3,A3依赖A4,……,A(m-1)依赖Am,而Am依赖A1,则称这m个软件包的依赖关系构成环),当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈,用户希望在安装和卸载某个软件包时,快速地知道这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包),你的任务就是实现这个部分。注意,安装一个已安装的软件包,或卸载一个未安装的软件包,都不会改变任何软件包的安装状态,即在此情况下,改变安装状态的软件包数为0。

输入格式

从文件manager.in中读入数据。

输入文件的第1行包含1个整数n,表示软件包的总数。软件包从0开始编号。

随后一行包含n−1个整数,相邻整数之间用单个空格隔开,分别表示1,2,3,⋯,n−2,n−1号软件包依赖的软件包的编号。

接下来一行包含1个整数q,表示询问的总数。之后q行,每行1个询问。询问分为两种:

install x:表示安装软件包x

uninstall x:表示卸载软件包x

你需要维护每个软件包的安装状态,一开始所有的软件包都处于未安装状态。

对于每个操作,你需要输出这步操作会改变多少个软件包的安装状态,随后应用这个操作(即改变你维护的安装状态)。

输出格式

输出到文件manager.out中。

输出文件包括q行。

输出文件的第i行输出1个整数,为第i步操作中改变安装状态的软件包数。

样例一

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

3
1
3
2
3

样例二

10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

1
3
2
1
3
1
1
1
0
1

值得注意的是标记方法,初始值为-1,这样可以下传0和1

Code

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
#include<bits/stdc++.h>
#define ll long long
#define reg register int
#define cl(x, y) memset(x, y, sizeof(x))
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

using std::swap;

inline int read() {
int k = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
k = k * 10 + ch - '0';
ch = getchar();
}
return k * f;
}

struct qaq{
int y, nt;
}e[200100];
int len = 0;
int lin[100100];

struct qwq{
int l, r;
int laz;
int sum;
}tree[400100];

int fa[100100], id[100100], son[100100];
int siz[100100], top[100100], dep[100100];
int tot = 0;

int n, m;
char ch[15];

void dfs(int x) {
siz[x] = 1;
son[x] = n;
for (reg i = lin[x]; i; i = e[i].nt) {
int y = e[i].y;
if (y != fa[x]) {
fa[y] = x;
dep[y] = dep[x] + 1;
dfs(y);
if (siz[y] > siz[son[x]]) son[x] = y;
siz[x] += siz[y];
}
}
}

void dfs2(int x, int p) {
id[x] = ++tot;
top[x] = p;
if (son[x] != n) dfs2(son[x], p);
for (reg i = lin[x]; i; i = e[i].nt) {
int y = e[i].y;
if (y != son[x] && y != fa[x]) dfs2(y, y);
}
}

void build(int p, int a, int b) {
tree[p].l = a;
tree[p].r = b;
tree[p].laz = -1;
if (a == b) return;
int mid = (a + b) >> 1;
build(ls(p), a, mid);
build(rs(p), mid + 1, b);
}

void pushdown(int p) {
if (tree[p].laz == -1) return;
else if (tree[p].laz == 1) {
tree[ls(p)].sum = tree[ls(p)].r - tree[ls(p)].l + 1;
tree[rs(p)].sum = tree[rs(p)].r - tree[rs(p)].l + 1;
tree[ls(p)].laz = 1;
tree[rs(p)].laz = 1;
tree[p].laz = -1;
}
else {
tree[ls(p)].sum = 0;
tree[rs(p)].sum = 0;
tree[ls(p)].laz = 0;
tree[rs(p)].laz = 0;
tree[p].laz = -1;
}
}

void update(int p, int a, int b, int v) {
int l = tree[p].l;
int r = tree[p].r;
if (r < a || l > b) return;
if (a <= l && r <= b) {
tree[p].laz = v;
tree[p].sum = v * (r - l + 1);
return;
}
pushdown(p);
update(ls(p), a, b, v);
update(rs(p), a, b, v);
tree[p].sum = tree[ls(p)].sum + tree[rs(p)].sum;
}

int get_sum(int p, int a, int b) {
int l = tree[p].l;
int r = tree[p].r;
if (r < a || l > b) return 0;
if (a <= l && r <= b) return tree[p].sum;
pushdown(p);
return get_sum(ls(p), a, b) + get_sum(rs(p), a, b);
}

int work(int x) {
int y = 0;
int ans = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
int temp = get_sum(1, id[top[x]], id[x]);
ans += temp;
update(1, id[top[x]], id[x], 1);
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
ans += get_sum(1, id[x], id[y]);
update(1, id[x], id[y], 1);
return ans;
}

inline void insert(int x, int y) {
e[++len].nt = lin[x];
lin[x] = len;
e[len].y = y;
}

int main() {
cl(fa, -1);
n = read();
for (reg i = 1; i < n; ++i) {
int x = read();
insert(x, i);
insert(i, x);
}
dfs(0);
dfs2(0, 0);
build(1, 1, n);
m = read();
for (reg i = 1; i <= m; ++i) {
scanf("%s", ch);
int x = read();
if (ch[0] == 'i') {
int ans = work(x);
printf("%d\n", dep[x] + 1 - ans);
}
else if (ch[0] == 'u') {
int ans = get_sum(1, id[x], id[x] + siz[x] - 1);
update(1, id[x], id[x] + siz[x] - 1, 0);
printf("%d\n", ans);
}
}
return 0;
}