[NOI2015] 软件包管理器
题目背景
Linux 用户和 OSX 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu 使用的 apt-get，Fedora/CentOS 使用的 yum，以及 OSX 下可用的 homebrew 都是优秀的软件包管理器。
题目描述
你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 \(a\) 依赖软件包 \(b\)，那么安装软件包 \(a\) 以前，必须先安装软件包 \(b\)。同时，如果想要卸载软件包 \(b\)，则必须卸载软件包 \(a\)。
现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 \(0\) 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 \(0\) 号软件包不依赖任何一个软件包。且依赖关系不存在环（即不会存在 \(m\) 个软件包 \(a_1,a_2, \dots , a_m\)，对于 \(i<m\)，\(a_i\) 依赖 \(a_{i+1}\)，而 \(a_m\) 依赖 \(a_1\) 的情况）。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。
注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 \(0\)。
输入格式
第一行一个正整数 \(n\)，表示软件包个数，从 \(0\) 开始编号。
第二行有 \(n-1\) 个整数，第 \(i\) 个表示 \(i\) 号软件包依赖的软件包编号。
然后一行一个正整数 \(q\)，表示操作个数，格式如下：
install x表示安装 \(x\) 号软件包uninstall x表示卸载 \(x\) 号软件包
一开始所有软件包都是未安装的。
对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。
输出格式
输出 \(q\) 行，每行一个整数，表示每次询问的答案。
样例 #1
样例输入 #1
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0
样例输出 #1
3
1
3
2
3
样例 #2
样例输入 #2
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
样例输出 #2
1
3
2
1
3
1
1
1
0
1
提示
一开始所有软件包都处于未安装状态。
安装 \(5\) 号软件包，需要安装 \(0,1,5\) 三个软件包。
之后安装 \(6\) 号软件包，只需要安装 \(6\) 号软件包。此时安装了 \(0,1,5,6\) 四个软件包。
卸载 \(1\) 号软件包需要卸载 \(1,5,6\) 三个软件包。此时只有 \(0\) 号软件包还处于安装状态。
之后安装 \(4\) 号软件包，需要安装 \(1,4\) 两个软件包。此时 \(0,1,4\) 处在安装状态。最后，卸载 \(0\) 号软件包会卸载所有的软件包。
【数据范围】
思路
一道简单的树链剖分 + 线段树。把树剖成链了之后用线段树维护区间和，表示区间内安装了多少软件。
我们只需要在更新前统计一共安装了多少软件，然后再在更新后统计一下，两者一减的差的绝对值就是会被改变安装状态的软件包的数量。
题目中软件编号从 \(0\) 开始一直到 \(n-1\)，不过我更习惯从 \(1\) 到 \(n\)，所以涉及编号的操作都加了一。
那么如何维护呢？
- 安装软件 \(x\)：安装一个软件只会影响其之前的依赖的状态，所以从根节点到 \(x\) 的路径上，所涉及的区间每个元素的值全部更新为 \(1\)。
- 卸载软件 \(x\)：卸载一个软件只会影响其之后的软件的状态，所以只需要把 \(x\) 的子树上的值全部改为 \(0\) 即可。
Code
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int n, q;
int stamp;
int father[maxn], son[maxn], size[maxn], depth[maxn], id[maxn], top[maxn];
int head[maxn];
struct Edge {
int from;
int to;
int next;
} edge[maxn << 1];
struct SegmentTree {
int left, right;
int value, tag;
} tree[maxn << 2];
inline void pushup(int root) {
tree[root].value = tree[root << 1].value + tree[root << 1 | 1].value;
}
inline void pushdown(int root, int l, int r) {
if (tree[root].tag == -1) return;
int mid = (l + r) >> 1;
tree[root << 1].value = tree[root].tag * (mid - l + 1);
tree[root << 1 | 1].value = tree[root].tag * (r - mid);
tree[root << 1].tag = tree[root].tag;
tree[root << 1 | 1].tag = tree[root].tag;
tree[root].tag = -1;
}
void build(int root, int l, int r) {
tree[root].left = l;
tree[root].right = r;
if (l == r) {
tree[root].value = 0;
tree[root].tag = -1;
return;
}
int mid = (l + r) >> 1;
build(root << 1, l, mid);
build(root << 1 | 1, mid + 1, r);
pushup(root);
}
void update(int root, int l, int r, int val) {
if (tree[root].left >= l && tree[root].right <= r) {
tree[root].value = val * (tree[root].right - tree[root].left + 1);
tree[root].tag = val;
return;
}
pushdown(root, tree[root].left, tree[root].right);
int mid = (tree[root].left + tree[root].right) >> 1;
if (mid >= l) update(root << 1, l, r, val);
if (mid < r) update(root << 1 | 1, l, r, val);
pushup(root);
}
int query(int root, int l, int r) {
if (tree[root].left >= l && tree[root].right <= r) {
return tree[root].value;
}
pushdown(root, tree[root].left, tree[root].right);
int mid = (tree[root].left + tree[root].right) >> 1;
int ans = 0;
if (mid >= l) ans += query(root << 1, l, r);
if (mid < r) ans += query(root << 1 | 1, l, r);
return ans;
}
inline void insertEdge(int u, int v) {
static int edgecnt;
edge[++edgecnt].from = u;
edge[edgecnt].to = v;
edge[edgecnt].next = head[u];
head[u] = edgecnt;
}
void dfs1(int u, int parent) {
father[u] = parent;
depth[u] = depth[parent] + 1;
size[u] = 1;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == parent) continue;
dfs1(v, u);
size[u] += size[v];
if (!son[u] || size[son[u]] < size[v]) {
son[u] = v;
}
}
}
void dfs2(int u, int utop) {
id[u] = ++stamp;
top[u] = utop;
if (!son[u]) return;
dfs2(son[u], utop);
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (v == father[u] || v == son[u]) continue;
dfs2(v, v);
}
}
inline void install(int u, int v) {
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) swap(u, v);
update(1, id[top[u]], id[u], 1);
u = father[top[u]];
}
if (depth[u] > depth[v]) swap(u, v);
update(1, id[u], id[v], 1);
}
inline void uninstall(int u) {
update(1, id[u], id[u] + size[u] - 1, 0);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n - 1; i++) {
int v;
scanf("%d", &v);
insertEdge(i + 1, v + 1);
insertEdge(v + 1, i + 1);
}
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, n);
scanf("%d", &q);
while (q--) {
char action[15];
int objective;
scanf("%s", action);
scanf("%d", &objective);
objective++;
if (action[0] == 'i') { // install
int before, after;
before = query(1, 1, n);
install(1, objective);
after = query(1, 1, n);
printf("%d\n", (int)abs(after - before));
} else {
int before, after;
before = query(1, 1, n);
uninstall(objective);
after = query(1, 1, n);
printf("%d\n", (int)abs(after - before));
}
}
return 0;
}