BZOJ 4196 [Noi2015]软件包管理器

题目大意

给你一些软件包之间的关系，安装时是安装根到它的链，卸载时是卸载它的子树，问每次安装和卸载的个数。

重读题没读懂……这题不是思博题嘛= =

树链剖分轻松搞定。

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxN 100010
#define lson pos<<1
#define rson pos<<1|1
int n,fa[maxN],son[maxN],q,inx,to[maxN<<1],nex[maxN<<1],head[maxN],tot;
int cnt,num[maxN],siz[maxN],sz[maxN<<2],laz[maxN<<2],depth[maxN],top[maxN];
char mode[10];
void addedge(int tx,int ty)
{
	to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;
	to[++tot]=tx,nex[tot]=head[ty],head[ty]=tot;
}
void dfs1(int pos)
{
	siz[pos]=1;
	depth[pos]=depth[fa[pos]]+1;
	for(int i=head[pos];i;i=nex[i])
		if(to[i]!=fa[pos])
		{
			dfs1(to[i]);
			siz[pos]+=siz[to[i]];
			if(siz[son[pos]]<siz[to[i]]) son[pos]=to[i];
		}
	return;
}
void dfs2(int pos,int pre)
{
	num[pos]=++cnt;
	top[pos]=pre;
	if(son[pos]) dfs2(son[pos],pre);
	for(int i=head[pos];i;i=nex[i])
		if(to[i]!=fa[pos]&&to[i]!=son[pos])
			dfs2(to[i],to[i]);
}
void pushdown(int pos,int l,int r)
{
	if(laz[pos]==1)
	{
		laz[lson]=laz[rson]=1;
		sz[lson]=sz[rson]=0;
		laz[pos]=0;
	}
	if(laz[pos]==2)
	{
		int mid=(l+r)>>1;
		laz[lson]=laz[rson]=2;
		sz[lson]=mid-l+1;
		sz[rson]=r-mid;
		laz[pos]=0;
	}
	return;
}
int query(int pos,int l,int r,int x,int y)
{
	if(x<=l&&r<=y) return sz[pos];
	pushdown(pos,l,r);
	int mid=(l+r)>>1,ret=0;
	if(x<=mid) ret+=query(lson,l,mid,x,y);
	if(y>mid) ret+=query(rson,mid+1,r,x,y);
	return ret;
}
void fill(int pos,int l,int r,int x,int y,int z)
{
	if(x<=l&&r<=y)
	{
		if(z==2)sz[pos]=r-l+1;
		else sz[pos]=0;
		laz[pos]=z;
		return;
	}
	pushdown(pos,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) fill(lson,l,mid,x,y,z);
	if(y>mid) fill(rson,mid+1,r,x,y,z);
	sz[pos]=sz[lson]+sz[rson];
}
int install(int tx)
{
	int ret=depth[tx];
	while(tx)
	{
		ret-=query(1,1,n,num[top[tx]],num[tx]);
		fill(1,1,n,num[top[tx]],num[tx],2);
		tx=fa[top[tx]];
	}
	return ret;
}
int uninstall(int tx)
{
	int ret=query(1,1,n,num[tx],num[tx]+siz[tx]-1);
	fill(1,1,n,num[tx],num[tx]+siz[tx]-1,1);
	return ret;
}
int main()
{
	scanf("%d",&n);
	for(int i=2;i<=n;++i) scanf("%d",fa+i),fa[i]++,addedge(i,fa[i]);
	dfs1(1);
	dfs2(1,1);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%s",mode);
		switch(mode[0])
		{
			case 'i':
			{
				scanf("%d",&inx);
				printf("%d\n",install(inx+1));
				break;
			}
			case 'u':
			{
				scanf("%d",&inx);
				printf("%d\n",uninstall(inx+1));
				break;
			}
		}
	}
	return 0;
}