8说了上代码
给定一棵树，两种操作
a x：x->root路径上的点权值置1
b x: 把x的子树所有结点权值置0
树上的区间更新操作，显然是要维护dfs
第一个操作暴力显然是t，用树剖把复杂度降到log^2n级
线段树上：区间置1|0
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
struct Edge{int to,nxt;}edge[maxn<<];
int head[maxn],tot,n,q; int f[maxn],son[maxn],size[maxn],d[maxn];
void dfs1(int x,int pre,int deep){
size[x]=;d[x]=deep;f[x]=pre;
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to;
if(y==pre)continue;
dfs1(y,x,deep+);
size[x]+=size[y];
if(size[y]>size[son[x]])son[x]=y;
}
}
int top[maxn],id[maxn],rk[maxn],cnt;
void dfs2(int x,int tp){
top[x]=tp;id[x]=++cnt;rk[cnt]=x;
if(son[x])dfs2(son[x],tp);
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to;
if(y!=son[x] && y!=f[x])dfs2(y,y);
}
} #define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int sum[maxn<<],lazy[maxn<<];
void pushup(int rt){sum[rt]=sum[rt<<]+sum[rt<<|];}
void pushdown(int l,int r,int rt){
if(lazy[rt]<)return;
if(lazy[rt]==){
lazy[rt<<]=lazy[rt<<|]=;
sum[rt<<]=sum[rt<<|]=;
lazy[rt]=-;
}
if(lazy[rt]==){
int m=l+r>>;
lazy[rt<<]=lazy[rt<<|]=;
sum[rt<<]=m-l+;sum[rt<<|]=r-m;
lazy[rt]=-;
}
}
void set0(int L,int R,int l,int r,int rt){
if(L<=l && R>=r){lazy[rt]=;sum[rt]=;return;}
pushdown(l,r,rt);
int m=l+r>>;
if(L<=m)set0(L,R,lson);
if(R>m)set0(L,R,rson);
pushup(rt);
}
void set1(int L,int R,int l,int r,int rt){
if(L<=l && R>=r){lazy[rt]=;sum[rt]=r-l+;return;}
pushdown(l,r,rt);
int m=l+r>>;
if(L<=m)set1(L,R,lson);
if(R>m)set1(L,R,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l &&R >=r)return sum[rt];
int m=l+r>>,res=;
pushdown(l,r,rt);
if(L<=m)res+=query(L,R,lson);
if(R>m)res+=query(L,R,rson);
return res;
} void Set1(int x,int y){
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]])swap(x,y);
set1(id[top[x]],id[x],,n,);
x=f[top[x]];
}
if(id[x]>id[y])swap(x,y);
set1(id[x],id[y],,n,);
}
int Query(int x,int y){
int res=;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]])swap(x,y);
res+=query(id[top[x]],id[x],,n,);
x=f[top[x]];
}
if(id[x]>id[y])swap(x,y);
return res+query(id[x],id[y],,n,);
} void init(){
memset(head,-,sizeof head);
memset(lazy,-,sizeof lazy);
tot=;
}
void addedge(int u,int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;
} int main(){
init();
cin>>n;
for(int u=;u<=n;u++){
int fa;scanf("%d",&fa);fa++;
addedge(fa,u);addedge(u,fa);
}
cnt=;dfs1(,,);dfs2(,); cin>>q;char op[];int x;
while(q--){
scanf("%s %d",op,&x);++x;
if(op[]=='i'){
int tmp=Query(x,);
cout<<d[x]-tmp<<'\n';
Set1(x,);
}
if(op[]=='u'){
cout<<query(id[x],id[x]+size[x]-,,n,)<<'\n';
set0(id[x],id[x]+size[x]-,,n,);
}
}
}