【NOI2015】【树链剖分】软件包管理器

【思路】
这是一道树链剖分的模板。
安装一个软件u，我们可以理解为修改从根节点到u的路径的值，即拆分路径跳重链进行修改。删除一个节点，我们可以理解为修改子树的权值，即修改[seg[u],seg[u]+size[u]-1]。当我们维护子树和以后，我们发现，答案就是操作前后整棵树的权值变化量。至此，这道题就可以做了。
代码：

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#define re register
#define lc (p<<1)
#define rc (p<<1|1)
#define len(p) (t[p].r-t[p].l+1)
using namespace std;
int a,b,c,n,m;
struct node{
	int u,v;
}e[1000001];
int f[1000001];
int nxp[1000001];
int cnt=0;
inline void add(int u,int v)
{
	e[++cnt].u=u;
	e[cnt].v=v;
	nxp[cnt]=f[u];
	f[u]=cnt;
}
struct tree{
	int l,r;
	int sum;
	int laz;
}t[4000001];
int son[1000001];
int siz[1000001];
int fa[1000001];
int rev[1000001];
int top[1000001];
int seg[1000001];
int dep[1000001];
void dfs1(int u,int ff)
{
	dep[u]=dep[ff]+1;
	siz[u]=1;
	fa[u]=ff;
	for(int re i=f[u];i;i=nxp[i])
	{
		int v=e[i].v;
		if(!siz[v])
		{
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[son[u]]<siz[v])son[u]=v;
		}
	}
}
int tot=0;
void dfs2(int u)
{
	if(son[u])
	{
		seg[son[u]]=++tot;
		rev[tot]=son[u];
		top[son[u]]=top[u];
		dfs2(son[u]);
	}
	for(int re i=f[u];i;i=nxp[i])
	{
		int v=e[i].v;
		if(!top[v])
		{
			seg[v]=++tot;
			rev[tot]=v;
			top[v]=v;
			dfs2(v);
		}
	}
}
void pushup(int p)
{
	t[p].sum=t[lc].sum+t[rc].sum;
}
void pushnow(int p,int c)
{
	t[p].sum=len(p)*c;
	t[p].laz=c;
}
void pushdown(int p)
{
	if(t[p].laz!=-1)
	{
		pushnow(lc,t[p].laz);
		pushnow(rc,t[p].laz);
		t[p].laz=-1;
	}
}
void build(int p,int l,int r)
{
	t[p].l=l;
	t[p].r=r;
	t[p].laz=-1;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(p);
}
void change(int p,int ql,int qr,int c)
{
	int l=t[p].l,r=t[p].r;
	if(ql<=l&&qr>=r)
	{
		pushnow(p,c);
		return;
	}
	pushdown(p);
	int mid=(l+r)>>1;
	if(ql<=mid)change(lc,ql,qr,c);
	if(qr>mid)change(rc,ql,qr,c);
	pushup(p);
}
void in(int x)
{
	int y=1;
	int fx=top[x];
	int fy=top[y];
	while(fx!=fy)
	{
		if(dep[fx]<dep[fy])
		{
			swap(x,y);
			swap(fx,fy);
		}
		change(1,seg[fx],seg[x],1);
		x=fa[fx];
		fx=top[x];
	}
	if(dep[x]>dep[y])swap(x,y);
	change(1,seg[x],seg[y],1);
}
char s[101];
int main()
{
	scanf("%d",&n);
	for(int re i=2;i<=n;i++)
	{
		scanf("%d",&a);a++;
		add(a,i);
		add(i,a);
	}
	rev[1]=tot=seg[1]=top[1]=1;
	dfs1(1,0);
	dfs2(1);
	build(1,1,tot);
	scanf("%d",&m);
	for(int re i=1;i<=m;i++)
	{
		scanf("%s",s);
		scanf("%d",&a);a++;
		int pre=t[1].sum;
		if(s[0]=='i')in(a);
		else change(1,seg[a],seg[a]+siz[a]-1,0);
		printf("%d\n",abs(t[1].sum-pre));
	}
}