【BZOJ4196】软件包管理器

    裸的树链剖分，就是再加一个修改子树的操作，子树在线段树里是连续的。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100010;

struct Segment_Tree
{
	int sum[maxn<<2];
	int tag_same[maxn<<2];
	int tag_clear[maxn<<2];
	int _l,_r;
	int n;
	
	#define ls (o<<1)
	#define rs ((o<<1)|1)
	#define mid ((l+r)>>1)

	void Mark_Clear(int o)
	{
		sum[o]=0;
		tag_same[o]=0;
		tag_clear[o]=1;
	}

	void Mark_Same(int o,int l,int r)
	{
		sum[o]=r-l+1;
		tag_clear[o]=0;
		tag_same[o]=1;
	}

	void Push_Down(int o,int l,int r)
	{
		if (l==r) return;
		if (tag_clear[o])
		{
			Mark_Clear(ls);
			Mark_Clear(rs);
			tag_clear[o]=0;
		}
		if (tag_same[o])
		{
			Mark_Same(ls,l,mid);
			Mark_Same(rs,mid+1,r);
			tag_same[o]=0;
		}
	}

	void Update(int o) {sum[o]=sum[ls]+sum[rs];}

	void Change_Same(int o,int l,int r)
	{
		if (_l<=l && r<=_r) {Mark_Same(o,l,r);return;}
		Push_Down(o,l,r);
		if (_l<=mid) Change_Same(ls,l,mid);
		if (_r>mid)  Change_Same(rs,mid+1,r);
		Update(o);
	}

	void Change_Clear(int o,int l,int r)
	{
		if (_l<=l && r<=_r) {Mark_Clear(o);return;}
		Push_Down(o,l,r);
		if (_l<=mid) Change_Clear(ls,l,mid);
		if (_r>mid)  Change_Clear(rs,mid+1,r);
		Update(o);
	}

	int Query(int o,int l,int r)
	{
		if (_l<=l && r<=_r) return sum[o];
		Push_Down(o,l,r);
		int res=0;
		if (_l<=mid) res+=Query(ls,l,mid);
		if (_r>mid)  res+=Query(rs,mid+1,r);
		Update(o);
		return res;
	}

	int Sum() {return sum[1];}
	void Change_Same(int _a,int _b) {_l=_a;_r=_b;Change_Same(1,1,n);}
	void Change_Clear(int _a,int _b) {_l=_a;_r=_b;Change_Clear(1,1,n);}
	#undef ls
	#undef rs
	#undef mid
}ST;

struct Tree
{
	int head[maxn],next[maxn<<1],E[maxn<<1],Ecnt;
	int fa[maxn],dep[maxn];
	int top[maxn],wson[maxn];
	int id[maxn],ids;
	int l[maxn],r[maxn];

	void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}

	int DFS1(int x,int father,int depth)
	{
		int sons=0,maxsons=0;
		fa[x]=father;dep[x]=depth;
		for (int i=head[x];i;i=next[i]) if (E[i]!=father)
		{
			int tsons=DFS1(E[i],x,depth+1);
			sons+=tsons;
			if (tsons>maxsons) maxsons=tsons,wson[x]=E[i];
		}
		return sons+1;
	}

	void DFS2(int x,int is_wson)
	{
		id[x]=++ids;
		l[x]=ids;
		if (is_wson) top[x]=top[fa[x]];else top[x]=x;
		if (wson[x]) DFS2(wson[x],1);
		for (int i=head[x];i;i=next[i]) if (E[i]!=fa[x] && E[i]!=wson[x]) DFS2(E[i],0);
		r[x]=ids;
	}

	void Build(int n)
	{
		(void)DFS1(0,0,1);
		DFS2(0,1);
		ST.n=n;
	}

	int Install(int x)
	{
		int pre=ST.Sum();
		while (x!=0) ST.Change_Same(id[top[x]],id[x]),x=fa[top[x]];
		ST.Change_Same(id[0],id[0]);
		return ST.Sum()-pre;
	}

	int Unistall(int x)
	{
		int pre=ST.Sum();
		ST.Change_Clear(l[x],r[x]);
		return pre-ST.Sum();
	}
}T;

void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())>='0' && ch<='9') x=x*10+ch-'0';}

char ctr[20];
int n,q;

int main()
{
	read(n);
	for (int i=1,y;i<n;i++) read(y),T.Add_Edge(i,y);
	T.Build(n);
	read(q);
	for (int i=1,x;i<=q;i++)
	{
		scanf("%s",ctr);
		read(x);
		if (ctr[0]=='i') printf("%d\n",T.Install(x));
		if (ctr[0]=='u') printf("%d\n",T.Unistall(x));
	}
	return 0;
}