# Paste: 软件包管理

Author: 66Leo66 c++ Tue, 12 Oct 2021 10:39:34
Plain Text |
```#include <bits/stdc++.h>
#define segmid ((l + r) >> 1)
using namespace std;
const int maxn = 400005;
int fa[maxn], dep[maxn], top[maxn], size[maxn], son[maxn], id[maxn], rnk[maxn],
cnt;
int ins[maxn];
vector<int> e[maxn];

int n, q;
namespace segtree {
int segins[maxn];
void build(int l, int r, int rt) {
if (l == r) {
segins[rt] = 0;
return;
}
build(l, segmid, rt * 2);
build(segmid + 1, r, rt * 2 + 1);
segins[rt] = 0;
}
void change(int l, int r, int x, bool val, int rt) {
if (l == r) {
segins[rt] = val;
return;
}
if (x <= segmid) {
change(l, segmid, x, val, rt * 2);

} else {
change(segmid + 1, r, x, val, rt * 2 + 1);
}
segins[rt] = segins[rt * 2] + segins[rt * 2 + 1];
}

int getSum(int l, int r, int u, int v, int rt) {
if (u > v) swap(u, v);
if (l == r) {
return segins[rt];
}
if (u > segmid) {
// ???
return getSum(segmid + 1, r, u, v, rt * 2 + 1);
} else if (v <= segmid) {
// ???
return getSum(l, segmid, u, v, rt * 2);
} else {
return getSum(l, segmid, u, segmid, rt * 2) +
getSum(segmid + 1, r, segmid + 1, v, rt * 2 + 1);
}
}
}  // namespace segtree

void dfs1(int x, int fat) {
fa[x] = fat;
dep[x] = dep[fat] + 1;
size[x] = 1;
for (int i = 0; i < e[x].size(); i++) {
int z = e[x][i];
if (z == fat) continue;
dfs1(z, x);
size[x] += size[z];
if (size[z] > size[son[x]]) son[x] = z;
}
}

void dfs2(int x, int topz) {
top[x] = topz;
id[x] = ++cnt;
rnk[cnt] = x;
if (son[x] == 0) return;
dfs2(son[x], topz);
for (int i = 0; i < e[x].size(); i++) {
int z = e[x][i];
if (z == fa[x]) continue;
if (son[x] != z) {
dfs2(z, z);
}
}
}
void treeUpdate(int u, int t) { segtree::change(1, n, id[u], t, 1); }
int treeQnodeCnt;
int treeNodeCnt(int x, int y) {
if (id[x] > id[y])
return id[x] - id[y] + 1;
else
return id[y] - id[x] + 1;
}
int treeQsum(int u, int v) {
treeQnodeCnt = 0;
int ans = 0;
while (top[u] != top[v]) {
// Chain Jump
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ans += segtree::getSum(1, n, id[top[u]], id[u], 1);
treeQnodeCnt += treeNodeCnt(top[u], u);
u = fa[top[u]];
}
treeQnodeCnt += treeNodeCnt(u, v);

return ans + segtree::getSum(1, n, id[u], id[v], 1);
}

void treeInstall(int u, int v) {
int temp1, temp2;
while (top[u] != top[v]) {
// Chain Jump
if (dep[top[u]] < dep[top[v]]) swap(u, v);
temp1 = id[u];
temp2 = id[top[u]];
if (temp1 > temp2) swap(temp1, temp2);
for (int i = temp1; i <= temp2; i++) {
segtree::change(1, n, i, 1, 1);
}

u = fa[top[u]];
}
temp1 = id[u];
temp2 = id[v];
if (temp1 > temp2) swap(temp1, temp2);
for (int i = temp1; i <= temp2; i++) {
segtree::change(1, n, i, 1, 1);
}
}

int treeUninstall(int x) {
int summ = 0;
segtree::change(1, n, id[x], 0, 1);
summ++;
// cout << "LOG uninstalled (" << x - 1 << ")" << endl;
for (int i = 0; i < e[x].size(); i++) {
int z = e[x][i];
if (z == fa[x] || !segtree::getSum(1, n, id[z], id[z], 1)) continue;
summ += treeUninstall(z);
}
return summ;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
{  // ??????
cin >> n;
for (int i = 2; i <= n; i++) {
int a;
cin >> a;
e[i].push_back(a + 1);
e[a + 1].push_back(i);
}
memset(segtree::segins, 0, maxn);

}  // ??????
n++;

{  // ????
dfs1(1, 0);
// cout << "[debug] dfs1 done" << endl;
dfs2(1, 1);
// cout << "[debug] dfs2 done" << endl;
segtree::build(1, n, 1);
//        for (int i = 1; i <= n; i++) {
//            cout << "SEGTREE info: " << segtree::getMax(1, n, i, i, 1)
//            << endl;
//        }
}  // ????

{  // ??
cin >> q;
while (q--) {
string op;
int u;
cin >> op >> u;
if (op == "install") {
if (segtree::getSum(1, n, id[u + 1], id[u + 1], 1)) {
cout << 0 << '\n';
continue;
}
int sum = treeQsum(1, u + 1);
cout << treeQnodeCnt - sum << '\n';
// treeUpdate(u + 1, 1);
treeInstall(1, u + 1);
} else {
if (!segtree::getSum(1, n, id[u + 1], id[u + 1], 1)) {
cout << 0 << '\n';
continue;
}
// op == "uninstall"
cout << treeUninstall(u + 1) << '\n';
}
}
}  // ??
return 0;
}```