本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-14 21:57:46

思路

对于 $a$ 依赖 $b$ 这种，就连一条 $a$ 与 $b$ 的边，可以发现最后会形成一颗以 $0$ 为根的树。

• 对于安装软件 $x$，显然 $0 \rightarrow x$ 路径上所有的软件都要安装，也就是将 $0 \rightarrow x$ 路径上所有点的权值变为 1
• 对于删除软件 $x$，就是将以 $x$ 为根的子树内的所有节点变为0

树链剖分即可。

代码

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=100005;
	int n,q;
	int head[maxn];
	struct EDGE
	{
		int to,nxt;
	}edge[maxn<<1];
	int cnt;
	inline void add(int u,int to)
	{
		edge[++cnt].to=to;
		edge[cnt].nxt=head[u];
		head[u]=cnt;
	} 
	int size[maxn<<3];
	int dfn[maxn<<3];
	int rank[maxn<<3];
	int hs[maxn<<3];
	int fa[maxn<<3];
	int nodecnt;
	int top[maxn<<3];
	int dep[maxn<<3];
	void dfs1(int u,int _fa)
	{
		dep[u]=dep[_fa]+1;
		size[u]=1;
		fa[u]=_fa;
		int imax=0;
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==_fa)continue;
			dfs1(to,u);
			size[u]+=size[to];
			if(size[to]>=imax)
			{
				imax=size[to];
				hs[u]=to;
			}
		}
	}
	void dfs2(int u,int _top)
	{
		dfn[u]=++nodecnt;
		rank[nodecnt]=u;
		top[u]=_top;
		if(hs[u])
		{
			dfs2(hs[u],_top);
		}
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==fa[u]||to==hs[u])continue;
			dfs2(to,to);
		}
	}
	int val[maxn<<3],lazy[maxn<<3];
	int L[maxn<<3],R[maxn<<3];
	void build(int pos,int l,int r)
	{
		L[pos]=l;
		R[pos]=r;
		lazy[pos]=-1;
		if(l==r)
		{
			return;
		}
		int mid=(l+r)>>1;
		build(pos<<1,l,mid);
		build(pos<<1|1,mid+1,r);
	}
	inline int get_len(int i)
	{
		return (R[i]-L[i]+1);
	}
	inline void push_down(int i)
	{
		if(lazy[i]==-1)return;
		lazy[i<<1]=lazy[i];
		lazy[i<<1|1]=lazy[i];
		val[i<<1]=lazy[i]*get_len(i<<1);
		val[i<<1|1]=lazy[i]*get_len(i<<1|1);
		lazy[i]=-1;
	}
	inline void push_up(int i)
	{
		val[i]=val[i<<1]+val[i<<1|1];
	}
	void modify(int pos,int _l,int _r,int l,int r,int _val)
	{
		if(_l>=l&&_r<=r)
		{
			lazy[pos]=_val;
			val[pos]=(_val)*get_len(pos);
			return;
		}
		if(_r<l||_l>r)return;
		push_down(pos);
		int mid=(_l+_r)>>1;
		if(mid>=l)modify(pos<<1,_l,mid,l,r,_val);
		if(mid<r)modify(pos<<1|1,mid+1,_r,l,r,_val);
		push_up(pos);
	}
	void Modify(int x,int y,int _val)
	{
		while(top[x]!=top[y])
		{
			if(dep[top[x]]<dep[top[y]])swap(x,y);
			modify(1,1,n,dfn[top[x]],dfn[x],_val);
			x=fa[top[x]];
		}
		if(dep[x]>dep[y])swap(x,y);
		modify(1,1,n,dfn[x],dfn[y],_val);
	}
	void main()
	{
		scanf("%d",&n);
		for(int i=1;i<n;i++)
		{
			int b;
			scanf("%d",&b);
			add(i,b);
			add(b,i);
		}
		dfs1(0,n*6);
		dfs2(0,0);
		build(1,1,n);
		\/\/-------------------
		char op[10];
		int x;
		scanf("%d",&q);
		for(int i=1;i<=q;i++)
		{
			scanf("%s%d",op,&x);
			if(op[0]=='i')
			{
				int ai=val[1];
				Modify(0,x,1);
				int bi=val[1];
				printf("%d\n",abs(ai-bi));
			}
			if(op[0]=='u')
			{
				int ai=val[1];
				modify(1,1,n,dfn[x],dfn[x]+size[x]-1,0);
				int bi=val[1];
				printf("%d\n",abs(ai-bi));
			}
		}		
	}
}
int main()
{
	Main::main();
	return 0;
}