链接：洛谷 P2146 [NOI2015]软件包管理器
题意：
共有 n n n个软件包，编号 0 0 0 ~ n ? 1 n-1 n?1，除 0 0 0号软件包以外的其他软件包均需要依赖其他软件包才能安装。所以，若要安装一个软件包，除 0 0 0号软件包外都需要已经安装了其依赖的软件包；若要卸载一个软件包，依赖该软件包的软件包都会被卸载。
有q个操作，分为如下 2 2 2种：
install x：表示安装软件包x
uninstall x：表示卸载软件包x
你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。
对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。
分析：
可以发现这其实是一棵以 0 0 0号结点为根的树，树的初始点权均为0。
-
安装 x x x：即将 x x x到根结点的点权全变为 1 1 1（注意不是加 1 1 1，因为有些点权已经是 1 1 1），随后输出 x x x到根结点的点权和的变化。
-
卸载 x x x：输出 x x x为根的子树点权和，随后将 x x x为根的子树的点权全部变为0（注意不是减 1 1 1，因为有些点权已经是 0 0 0）
树链剖分后进行如上操作即可，同时注意线段树懒标记在该题中的使用
以下代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+50;
int n,q;
//**************建树**************************
struct edge
{
int u;int v;int next;
}e[maxn<<1];
int head[maxn],cnt;
void add_edge(int u,int v)
{
e[cnt]=edge{
u,v,head[u]};head[u]=cnt++;e[cnt]=edge{
v,u,head[v]};head[v]=cnt++;
}
//**************树链剖分***********************
int fa[maxn],sz[maxn],son[maxn];
void dfs1(int u,int pre)
{
fa[u]=pre;sz[u]=1;for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;if(v==pre)continue;dfs1(v,u);sz[u]+=sz[v];if(sz[v]>sz[son[u]])son[u]=v;}
}
int id[maxn],top[maxn],tot;
void dfs2(int u,int TOP)
{
top[u]=TOP;id[u]=++tot;if(!son[u])return;dfs2(son[u],TOP);for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;if(v!=son[u]&&v!=fa[u])dfs2(v,v);}
}
//******************线段树*********************
#define ls rt<<1
#define rs rt<<1|1
struct seg_tree
{
int sum; //记录区间点权和int laz; //记录待向下传递的操作（全变为0，还是全变为1）
}t[maxn<<2];
void push_up(int rt)
{
t[rt].sum=t[ls].sum+t[rs].sum;
}
void push_down(int rt,int l,int r)
{
if(!t[rt].laz)return;t[ls].laz=t[rs].laz=t[rt].laz; //懒标记下传if(t[rt].laz==1) //laz=1表示区间全部变为1{
int mid=(l+r)>>1;t[ls].sum=mid-l+1;t[rs].sum=r-mid;}else //laz=-1表示区间全部变为0{
t[ls].sum=0;t[rs].sum=0;}t[rt].laz=0;
}
void build(int rt,int l,int r)
{
t[rt].sum=t[rt].laz=0; //清空线段树if(l==r)return;int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);
}
void updata(int rt,int l,int r,int ql,int qr,int op)
{
if(ql<=l&&r<=qr){
t[rt].laz=op;if(op==1)t[rt].sum=r-l+1; //op=1表示区间全部变为1elset[rt].sum=0; //op=-1表示区间全部变为0return;}push_down(rt,l,r);int mid=(l+r)>>1;if(ql<=mid)updata(ls,l,mid,ql,qr,op);if(qr>mid)updata(rs,mid+1,r,ql,qr,op);push_up(rt);
}
int query(int rt,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr)return t[rt].sum;push_down(rt,l,r);int mid=(l+r)>>1;int res=0;if(ql<=mid)res+=query(ls,l,mid,ql,qr);if(qr>mid)res+=query(rs,mid+1,r,ql,qr);return res;
}
//******************树上操作*********************
int install(int x)
{
int temp=t[id[1]].sum;while(top[x]!=top[1]){
updata(1,1,n,id[top[x]],id[x],1);x=fa[top[x]];}updata(1,1,n,id[1],id[x],1);return t[id[1]].sum-temp;
}
int uninstall(int x)
{
int temp=query(1,1,n,id[x],id[x]+sz[x]-1);updata(1,1,n,id[x],id[x]+sz[x]-1,-1);return temp;
}
//*****************初始化**********************
void init()
{
memset(head,-1,sizeof(head));cnt=0;memset(son,0,sizeof(son));tot=0;
}
//******************************************
int main()
{
init();scanf("%d",&n);for(int i=1;i<=n-1;i++){
int a;scanf("%d",&a);add_edge(i+1,a+1); //从0开始编号改为从1开始编号，更好处理} //根结点变为1dfs1(1,-1);dfs2(1,1);build(1,1,n);scanf("%d",&q);while(q--){
char op[20];int x;scanf("%s %d",op,&x);if(op[0]=='i')printf("%d\n",install(x+1));elseprintf("%d\n",uninstall(x+1));}return 0;
}