lp2146 NOI2015 软件包管理器

简化题意：
存在一棵树，其上所有点的初始值为0。
存在两种操作，分别是，将一个点的所有父亲节点改为1，或者将一个点的所有儿子节点改为0。
要求维护这个修改，并能得知每一次修改的节点个数。
当然地，考虑到这棵树是静态的，我们可以预处理出每个点的子树大小和它到根的路径长度。
于是，问题就转化为：
把目标节点到根节点的所有点变成1，把目标节点的子树变成0，查询目标节点到根节点的1的数量，查询目标节点的子树的1的数量。
这个问题似乎有些困难。我们考虑它的弱化版，也就是只有目标节点到根节点的这样一种情况。
显然，只需要上一个树剖就可以解决问题。
那么加上子树修改呢？
我们意识到一个很有趣的事情，那就是，一棵子树中的点，在树剖后，仍然是DFS序序列上连续的一段。又，这一段的长度显然是子树大小，由此问题可解。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt) 

const int N=100005;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
int n,q;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}
int sz[N],sn[N],dep[N],fa[N];
inline void dfs0(int X,int FA){
	sz[X]=1,sn[X]=0,dep[X]=dep[FA]+1,fa[X]=FA;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
int dfn[N],cnt=0,tp[N]; 
inline void dfs1(int X,int FA,int TP){
	tp[X]=TP,dfn[X]=++cnt;
	if(sn[X]){
		dfs1(sn[X],X,TP);
	}
	Fv(i,X){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,X,e[i].v);
	}
}

#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
int tr[N<<2],tg[N<<2];
inline void rnw(int X,int L,int R,int C){
	tr[X]=LEN*C,tg[X]=C+1;
}
inline void updt(int X,int L,int R){
	tr[X]=tr[LS]+tr[RS];
}
inline void pshd(int X,int L,int R){
	if(tg[X]){
		rnw(LS,L,MID,tg[X]-1),rnw(RS,MID+1,R,tg[X]-1);
		tg[X]=0;
	}
}
inline void chg(int X,int L,int R,int A,int B,int C){
	if(A<=L&&R<=B){
		rnw(X,L,R,C);
		return;
	}
	if(R<A||L>B){
		return;
	}
	pshd(X,L,R);
	chg(LS,L,MID,A,B,C),chg(RS,MID+1,R,A,B,C);
	updt(X,L,R);
}
inline int qry(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		return tr[X];
	}
	if(R<A||L>B){
		return 0;
	}
	pshd(X,L,R);
	return qry(LS,L,MID,A,B)+qry(RS,MID+1,R,A,B);
}

inline int dwqry(int X){
	return qry(1,1,n,dfn[X],dfn[X]+sz[X]-1);
}
inline void dwchg(int X){
	chg(1,1,n,dfn[X],dfn[X]+sz[X]-1,0);
}
inline int up(int X){
	int RT=0;
	while(X){
		RT-=qry(1,1,n,dfn[tp[X]],dfn[X]);
		RT+=dfn[X]-dfn[tp[X]]+1;
		chg(1,1,n,dfn[tp[X]],dfn[X],1);
		X=fa[tp[X]];
	}
	
	return RT;
}
void init(){
	scanf("%d",&n);
	int x;
	for(int i=1;i<n;++i){
		scanf("%d",&x);
		add(i+1,x+1);
	}
	dfs0(1,0);
	dfs1(1,0,1);
	scanf("%d",&q);
	char ch[10];
	for(int i=1;i<=q;++i){
		std::cin>>ch+1;
		scanf("%d",&x);
		++x;
		if(ch[1]=='i'){
			printf("%d\n",up(x));
		}else{
			printf("%d\n",dwqry(x));
			dwchg(x);
		}
	}
}
int main(){
	init();
	return 0;
}