[bzoj4196]-[NOI2015]软件包管理器

题目（bzoj）
题目（洛谷）
又一道树剖裸题......
处理一下细节即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#define ls id<<1
#define rs id<<1|1
#define N 100005
using namespace std;
template <class _E> inline void read(_E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck)e=-e;
}
int n,Q;
struct edge{int vk;int nxt;}e[N<<1];
int tt,head[N];
inline void ad(int u,int v){e[++tt].vk=v;e[tt].nxt=head[u];head[u]=tt;}
int siz[N],top[N],son[N],rank[N],f[N],idx;
int out[N];
void dfs1(int u,int fa)
{
	siz[u]=1,f[u]=fa;
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (v==fa) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if (!son[u] || siz[v]>siz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int fa)
{
	top[u]=fa;
	rank[u]=++idx;
	if (!son[u])
	{
		out[u]=idx;
		return;
	}
	dfs2(son[u],fa);
	for (int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].vk;
		if (v==f[u] || v==son[u]) continue;
		dfs2(v,v);
	}
	out[u]=idx;
}
struct Segment_tree{
	int lazy[N<<2],ll[N<<2],rr[N<<2],sum[N<<2];
	inline void up(int id){sum[id]=sum[id<<1]+sum[id<<1|1];}
	inline void down(int id)
	{
		if (lazy[id]!=-1)
		{
			lazy[id<<1]=lazy[id];
			lazy[id<<1|1]=lazy[id];
			sum[id<<1]=lazy[id]*(rr[id<<1]-ll[id<<1]+1);
			sum[id<<1|1]=lazy[id]*(rr[id<<1|1]-ll[id<<1|1]+1);
			lazy[id]=-1;
		}
	}
	void build(int l,int r,int id)
	{
		ll[id]=l,rr[id]=r;lazy[id]=-1;
		if (l==r) return;
		int mid=(l+r)>>1;
		build(l,mid,ls),build(mid+1,r,rs);
	}
	void update(int val,int id,int L,int R)
	{
		int l=ll[id],r=rr[id];
		if (L>r || R<l) return;
		if (L<=l && R>=r)
		{
			lazy[id]=val;
			sum[id]=val*(r-l+1);
			return;
		}
		down(id);
		update(val,ls,L,R);
		update(val,rs,L,R);
		up(id);
	}
	int query(int id,int L,int R)
	{
		int l=ll[id],r=rr[id];
		if (L>r || R<l) return 0;
		if (L<=l && R>=r) return sum[id];
		down(id);
		int ret=0;
		ret+=query(ls,L,R);
		ret+=query(rs,L,R);
		return ret;
	}
}tree;
inline int install(int x)
{
	int f1=top[x],ret=0;
	while (x)
	{
		ret+=(rank[x]-rank[f1]+1)-tree.query(1,rank[f1],rank[x]);
		tree.update(1,1,rank[f1],rank[x]);
		x=f[f1];f1=top[x];
	}
	return ret;
}
inline int uninstall(int x)
{
	int ret=tree.query(1,rank[x],out[x]);
	tree.update(0,1,rank[x],out[x]);
	return ret;
}
char s[15];
int main()
{
	read(n);int belong;
	for (int i=1;i<n;++i)
	{
		read(belong);
		ad(i+1,belong+1),ad(belong+1,i+1);
	}
	dfs1(1,0);dfs2(1,1);
	tree.build(1,n,1);
	read(Q);
	int xx;
	while (Q--)
	{
		scanf("%s%d",s,&xx);++xx;
		if (s[0]=='i') printf("%d\n",install(xx));
		else printf("%d\n",uninstall(xx));
	}
	return 0;
}