题目大意：
题目链接：https://www.luogu.org/problem/P2146
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，……，Am−1依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。
思路：
- 默写树剖板子
显然，删除一个软件就相当于要删除所有依赖他的软件，也就是求的子树大小；增加一个软件就相当于要把路径全部增加，即求一条路径的节点个数。
每一次都修改树显然是不够优秀的。我们可以考虑直接把树建好，然后每一个节点维护一个权值，表示这个节点现在是否真实存在。
删除一个节点就只要求出以该节点为根的子树内权值为1的节点个数，增加一个节点就只要求路径的权值为0的点的个数。
那么问题就是一个树剖的板子了。线段树维护区间和，每次询问之后打一个标记即可。
感觉现在做的树剖题目都很裸啊，到时候要拐一点弯的题就完了啊。
时间复杂度
代码：
成功写进行233
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=200010;
int fa[N],son[N],dep[N],top[N],size[N],id[N],head[N];
int n,tot,cnt,m,x;
char ch[20];
struct edge
{
int next,to;
}e[N];
struct Treenode
{
int l,r,sum,lazy;
};
struct Tree
{
Treenode tree[N*4];
void pushdown(int x)
{
if (tree[x].lazy!=-1)
{
tree[x*2].lazy=tree[x*2+1].lazy=tree[x].lazy;
if (!tree[x].lazy) tree[x*2].sum=tree[x*2+1].sum=0;
else
{
tree[x*2].sum=tree[x*2].r-tree[x*2].l+1;
tree[x*2+1].sum=tree[x*2+1].r-tree[x*2+1].l+1;
}
tree[x].lazy=-1;
}
}
void pushup(int x)
{
tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;
}
void build(int x)
{
tree[x].lazy=-1;
if (tree[x].l==tree[x].r) return;
int mid=(tree[x].l+tree[x].r)>>1;
tree[x*2].l=tree[x].l;
tree[x*2].r=mid;
tree[x*2+1].l=mid+1;
tree[x*2+1].r=tree[x].r;
build(x*2); build(x*2+1);
}
int update(int x,int l,int r,int val)
{
if (tree[x].l==l && tree[x].r==r)
{
int s=tree[x].sum;
tree[x].lazy=val;
if (!val) tree[x].sum=0;
else tree[x].sum=tree[x].r-tree[x].l+1;
return s;
}
pushdown(x);
int mid=(tree[x].l+tree[x].r)>>1,ans=0;
if (r<=mid) ans=update(x*2,l,r,val);
else if (l>mid) ans=update(x*2+1,l,r,val);
else ans=update(x*2,l,mid,val)+update(x*2+1,mid+1,r,val);
pushup(x);
return ans;
}
}Tree;
void add(int from,int to)
{
e[++tot].to=to;
e[tot].next=head[from];
head[from]=tot;
}
void dfs1(int x)
{
size[x]=1; dep[x]=dep[fa[x]]+1;
for (int i=head[x];~i;i=e[i].next)
{
int y=e[i].to;
dfs1(y);
size[x]+=size[y];
if (size[y]>size[son[x]]) son[x]=y;
}
}
void dfs2(int x,int tp)
{
top[x]=tp; id[x]=++cnt;
if (son[x]) dfs2(son[x],tp);
for (int i=head[x];~i;i=e[i].next)
{
int y=e[i].to;
if (y!=son[x]) dfs2(y,y);
}
}
int insert(int x,int y)
{
int sum=0;
while (top[x]!=top[y])
{
if (dep[top[x]]<dep[top[y]]) swap(x,y);
sum+=id[x]-id[top[x]]+1-Tree.update(1,id[top[x]],id[x],1);
x=fa[top[x]];
}
if (dep[x]<dep[y]) swap(x,y);
sum+=id[x]-id[y]+1-Tree.update(1,id[y],id[x],1);
return sum;
}
int del(int x)
{
return Tree.update(1,id[x],id[x]+size[x]-1,0);
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d",&n);
for (int i=2;i<=n;i++)
{
scanf("%d",&fa[i]);
fa[i]++;
add(fa[i],i);
}
dfs1(1); dfs2(1,1);
Tree.tree[1].l=1; Tree.tree[1].r=n;
Tree.build(1);
scanf("%d
",&m);
while (m--)
{
scanf("%s%d",ch+1,&x);
x++;
if (ch[1]=='i')
printf("%d
",insert(1,x));
else
printf("%d
",del(x));
}
return 0;
}