题意：
给你一棵树，有2种操作：
1.使得某个点到根节点路径上的所有点权值赋为1。
2.使得某节点的子树中所有节点权值赋为0.
每次操作要求输出权值更改的节点个数。
解题思路：
显然是用树剖来解决问题，考虑用区间赋值的线段树维护区间内1的个数，然后直接按题意树剖求解即可。
操作1的时间效率为\( O ( \log^{2} n) \) ,操作2的时间效率为\( O( \log n) \) ,总时间复杂度最坏为\( O (m \log^{2} n) \).
BZOJ上跑了5900ms，6960KB
#include <stdio.h>
#define MN 100005
#define Mn (1<<17)
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define v edge[i].to
int mark[Mn<<],sum[Mn<<],siz[MN],dep[MN],son[MN],fa[MN],top[MN],head[MN],cnt,n,q,dfsn,l[MN],r[MN];
struct zxy{int to,nxt;}edge[MN];
inline void ins(int x,int y){edge[++cnt].to=y,edge[cnt].nxt=head[x],head[x]=cnt;}
inline int in(){
int x=,f=;char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x*f;
}
inline void dfs1(int u,int d){
dep[u]=d,siz[u]=,son[u]=-;
for (register int i=head[u]; i; i=edge[i].nxt){
dfs1(v,d+);siz[u]+=siz[v];
if (son[u]==-||siz[v]>siz[son[u]]) son[u]=v;
}
}
inline void dfs2(int u,int tp){
top[u]=tp;l[u]=(++dfsn);if (son[u]!=-) dfs2(son[u],tp);
for (register int i=head[u]; i; i=edge[i].nxt)
if (v!=son[u]) dfs2(v,v);r[u]=dfsn;
}
inline void pushdown(int k,int l,int r){
if (mark[k]==-)return;
register int x=r-l+;mark[ls]=mark[rs]=mark[k];
sum[ls]=mark[k]*(x-(x>>));sum[rs]=mark[k]*(x>>);mark[k]=-;
}
inline void A(int l,int r,int a,int b,int k,int ad){
if (a<=l&&r<=b) {mark[k]=ad; sum[k]=(r-l+)*ad;return;}
pushdown(k,l,r);if (a<=mid) A(l,mid,a,b,ls,ad);
if (b>mid) A(mid+,r,a,b,rs,ad);sum[k]=sum[ls]+sum[rs];
}
inline int Q(int l,int r,int a,int b,int k){
if (a==l&&b==r) return sum[k];pushdown(k,l,r);
if (b<=mid) return Q(l,mid,a,b,ls);
if (mid<a) return Q(mid+,r,a,b,rs);
return Q(l,mid,a,mid,ls)+Q (mid+,r,mid+,b,rs);
}
inline int install(int x){
register int res=;
while (top[x]) res+=l[x]-l[top[x]]-Q(,n,l[top[x]],l[x],)+,A(,n,l[top[x]],l[x],,),x=fa[top[x]];
res+=l[x]-l[]+-Q(,n,l[],l[x],);A(,n,l[],l[x],,);return res;
}
inline int uninstall(int x){
register int res=Q(,n,l[x],r[x],);
A(,n,l[x],r[x],,);return res;
}
void init(){
n=in();for (register int i=; i<n; ++i) fa[i]=in(),ins(fa[i],i);
dfs1(,);dfs2(,);
}
void solve(){
for (q=in(); q--;){
register char op[];scanf("%s",op);register int x=in();
if (op[]=='i') printf("%d\n",install(x));
else printf("%d\n",uninstall(x));
}
}
int main(){init();solve();return ;}