题目背景
Linux 用户和 OSX 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu 使用的 apt-get，Fedora/CentOS 使用的 yum，以及 OSX 下可用的 homebrew 都是优秀的软件包管理器。
题目描述
你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 aa 依赖软件包 bb，那么安装软件包 aa 以前，必须先安装软件包 bb。同时，如果想要卸载软件包 bb，则必须卸载软件包 aa。
现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 00 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 00 号软件包不依赖任何一个软件包。且依赖关系不存在环（即不会存在 mm 个软件包 a_1,a_2, dots , a_ma1,a2,…,am，对于 i<mi<m，a_iai 依赖 a_i+1ai+1，而 a_mam 依赖 a_1a1 的情况）。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。
注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 00。
输入格式
第一行一个正整数 nn，表示软件包个数，从 00 开始编号。
第二行有 n-1n−1 个整数，第 ii 个表示 ii 号软件包依赖的软件包编号。
然后一行一个正整数 qq，表示操作个数，格式如下：
install x表示安装 xx 号软件包uninstall x表示卸载 xx 号软件包
一开始所有软件包都是未安装的。
对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。
输出格式
输出 qq 行，每行一个整数，表示每次询问的答案。
输入输出样例
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 03
1
3
2
310
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 91
3
2
1
3
1
1
1
0
1一眼看去似乎没办法单独开个数组维护每个点的状态(安装/未安装), 实际上我们浪费点时间单点查询一下也不会超时
查到状态以后再树剖查询结果就出来了
注: 查询时的区间一定要是$[ id[l], id[r] ], query(id[l], id[r], 1, n, 1)$, 而不是$[l, r], query(l, r, 1, n, 1)$
前者是dfs序下标, 而后者只是一般情况下的区间下标! 后者虽然说可能能过所有样例, 但这样查询到的结果是不正确的, 一定要记得用$id[l], id[r]$作为区间左右端点, 因为我们线段树里是按dfs序来存的的
如果过了样例却过不了题可以看看是不是犯了上面这个错误
ac code#include <iostream>
#include <algorithm>
using namespace std;
typedef int nit, it, itn;
typedef long long ll;
constexpr int MAXN = 1e5 + 7, inf = 0x3f3f3f3f;
ll sum[MAXN << 2], lazy[MAXN << 2], a[MAXN], nid[MAXN], n, m;
int h[MAXN], ne[MAXN << 1], e[MAXN << 1], at[MAXN], idx;
int top[MAXN], id[MAXN], son[MAXN], tmp[MAXN], R[MAXN], fa[MAXN], Size[MAXN], deep[MAXN], cnt, ncnt;
void add(int u, int v)
{
e[++idx] = v;
ne[idx] = h[u];
h[u] = idx;
}
void pushup(int rt)
{
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void pushdown(int rt, int len)
{
if (lazy[rt])
{
lazy[rt << 1] = lazy[rt];
lazy[rt << 1 | 1] = lazy[rt];
sum[rt << 1] = lazy[rt] == 1 ? len - (len >> 1) : 0;
sum[rt << 1 | 1] = lazy[rt] == 1 ? len >> 1 : 0;
lazy[rt] = 0;
}
}
void build(int l, int r, int rt)
{
if (l == r)
{
sum[rt] = 0;
return;
}
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushup(rt);
}
ll query(int a, int b, int l, int r, int rt)
{
if (a <= l && r <= b)
return sum[rt];
pushdown(rt, r - l + 1);
ll ans = 0;
int mid = l + r >> 1;
if (a <= mid)
ans += query(a, b, l, mid, rt << 1);
if (b > mid)
ans += query(a, b, mid + 1, r, rt << 1 | 1);
return ans;
}
void update(int pos, int c)
{
sum[nid[pos]] += c;
int t = nid[pos] >> 1, Size = 2;
while (t)
{
pushup(t);
pushdown(t, Size);
t >>= 1;
Size <<= 1;
}
}
void update(int a, int b, int install, int l, int r, int rt)
{
if (a <= l && r <= b)
{
if (install == 1)
sum[rt] = r - l + 1;
else
sum[rt] = 0;
lazy[rt] = install;
return;
}
pushdown(rt, r - l + 1);
int mid = l + r >> 1;
if (a <= mid)
update(a, b, install, l, mid, rt << 1);
if (b > mid)
update(a, b, install, mid + 1, r, rt << 1 | 1);
pushup(rt);
}
ll pathquery(int x, int y, int install)
{
ll ans = 0, tmp;
while (top[x] != top[y])
{
if (deep[top[x]] < deep[top[y]])
{
swap(x, y);
}
tmp = query(id[top[x]], id[x], 1, n, 1);
ans += (install == 1 ? id[x] - id[top[x]] + 1 - tmp : tmp);
x = fa[top[x]];
}
if (deep[x] > deep[y])
swap(x, y);
tmp = query(id[x], id[y], 1, n, 1);
ans += (install == 1 ? id[y] - id[x] + 1 - tmp : tmp);
return ans;
}
void pathupdate(int x, int y, int install)
{
while (top[x] != top[y])
{
if (deep[top[x]] < deep[top[y]])
{
swap(x, y);
}
update(id[top[x]], id[x], install, 1, n, 1);
x = fa[top[x]];
}
if (deep[x] > deep[y])
swap(x, y);
update(id[x], id[y], install, 1, n, 1);
}
void sonupdate(int x, int install)
{
update(id[x], id[x] + Size[x] - 1, install, 1, n, 1);
}
ll sonquery(int x)
{
return query(id[x], id[x] + Size[x] - 1, 1, n, 1);
}
void dfs1(int x, int f, int dep)
{
deep[x] = dep;
Size[x] = 1;
fa[x] = f;
int maxson = -1;
for (int i = h[x]; i; i = ne[i])
{
int y = e[i];
if (y != f)
{
dfs1(y, x, dep + 1);
Size[x] += Size[y];
if (maxson < Size[y])
{
son[x] = y;
maxson = Size[y];
}
}
}
}
void dfs2(int x, int f)
{
id[x] = ++cnt;
at[cnt] = a[x];
tmp[cnt] = x;
top[x] = f;
if (!son[x])
return;
dfs2(son[x], f);
for (int i = h[x]; i; i = ne[i])
{
int y = e[i];
if (y != fa[x] && y != son[x])
dfs2(y, y);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int pos, t, l, r, u, v, rt = 1;
ll x, ans;
string op;
cin >> n;
for (int i = 2; i <= n; ++i)
{
cin >> u;
u++;
add(i, u);
add(u, i);
}
dfs1(rt, 0, 1);
dfs2(rt, rt);
build(1, n, 1);
cin >> m;
while (m--)
{
ans = 0;
cin >> op >> pos;
pos++;
int vis = query(id[pos], id[pos], 1, n, 1);
if (op[0] == 'i' && !vis)
{
ans = pathquery(pos, rt, 1);
pathupdate(pos, rt, 1);
}
else if (op[0] == 'u' && vis)
{
ans = sonquery(pos);
sonupdate(pos, -1);
}
cout << ans << '
';
}
return 0;
}