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<<1]; 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]=1;d[x]=deep;f[x]=pre; for(int i=head[x];i!=-1;i=edge[i].nxt){ int y=edge[i].to; if(y==pre)continue; dfs1(y,x,deep+1); 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!=-1;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<<2],lazy[maxn<<2]; void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];} void pushdown(int l,int r,int rt){ if(lazy[rt]<0)return; if(lazy[rt]==0){ lazy[rt<<1]=lazy[rt<<1|1]=0; sum[rt<<1]=sum[rt<<1|1]=0; lazy[rt]=-1; } if(lazy[rt]==1){ int m=l+r>>1; lazy[rt<<1]=lazy[rt<<1|1]=1; sum[rt<<1]=m-l+1;sum[rt<<1|1]=r-m; lazy[rt]=-1; } } void set0(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){lazy[rt]=0;sum[rt]=0;return;} pushdown(l,r,rt); int m=l+r>>1; 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]=1;sum[rt]=r-l+1;return;} pushdown(l,r,rt); int m=l+r>>1; 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>>1,res=0; 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],1,n,1); x=f[top[x]]; } if(id[x]>id[y])swap(x,y); set1(id[x],id[y],1,n,1); } int Query(int x,int y){ int res=0; while(top[x]!=top[y]){ if(d[top[x]]<d[top[y]])swap(x,y); res+=query(id[top[x]],id[x],1,n,1); x=f[top[x]]; } if(id[x]>id[y])swap(x,y); return res+query(id[x],id[y],1,n,1); } void init(){ memset(head,-1,sizeof head); memset(lazy,-1,sizeof lazy); tot=0; } 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=2;u<=n;u++){ int fa;scanf("%d",&fa);fa++; addedge(fa,u);addedge(u,fa); } cnt=0;dfs1(1,0,1);dfs2(1,1); cin>>q;char op[20];int x; while(q--){ scanf("%s %d",op,&x);++x; if(op[0]=='i'){ int tmp=Query(x,1); cout<<d[x]-tmp<<' '; Set1(x,1); } if(op[0]=='u'){ cout<<query(id[x],id[x]+size[x]-1,1,n,1)<<' '; set0(id[x],id[x]+size[x]-1,1,n,1); } } }