题面
解析
事实上,这应该是道树剖裸题了,
将已安装表示为(1),
那么只需要在线段树中记录一下区间中(1)的个数就行了.
在询问的时候,
如果是安装,就查询(x)到根节点,
卸载的话,就查询(x)的子树.
注意下细节就行了(最好整体位移一下).
感觉真的没什么讲的了qwq
上代码吧:
#include <iostream>
#include <cstdio>
#include <cstring>
#define ls(a) a<<1
#define rs(a) a<<1|1
using namespace std;
inline int read(){
int sum=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}
struct edge{int to,next;}e[100001];
struct node{int dep,top,fa,son,size,id;}a[100001];
struct tree{int l,r,val,tag;}t[400001];
int n,m;
int head[100001],cnt=0;
int tot=0;
inline void add(int x,int y){
e[++cnt]=(edge){head[x],y};head[x]=cnt;
}
void dfs1(int x,int fa){
a[x].dep=a[fa].dep+1;a[x].fa=fa;a[x].size=1;
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;if(k==fa) continue;
dfs1(k,x);a[x].size+=a[k].size;
if(!a[x].son||a[a[x].son].size<a[k].size) a[x].son=k;
}
}
void dfs2(int x,int t){
a[x].id=++tot;a[x].top=t;
if(a[x].son) dfs2(a[x].son,t);
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;if(k==a[x].fa||k==a[x].son) continue;
dfs2(k,k);
}
}
void pushup(int p){
t[p].val=t[ls(p)].val+t[rs(p)].val;
}
void pushdown(int p){
if(!t[p].tag) return ;
int ls=ls(p),rs=rs(p);
t[ls].tag=t[rs].tag=t[p].tag;
if(t[p].tag==2) t[p].tag=0;
t[ls].val=t[p].tag*(t[ls].r-t[ls].l+1);
t[rs].val=t[p].tag*(t[rs].r-t[rs].l+1);
t[p].tag=0;
}
void build(int p,int l,int r){
t[p].l=l;t[p].r=r;
if(l==r) return ;
int mid=(l+r)>>1;
build(ls(p),l,mid);build(rs(p),mid+1,r);
}
void change(int p,int l,int r,int opt){
if(t[p].l>=l&&t[p].r<=r){
t[p].val=opt*(t[p].r-t[p].l+1);t[p].tag=opt;
if(!opt) t[p].tag=2;
return ;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid) change(ls(p),l,r,opt);
if(r>mid) change(rs(p),l,r,opt);
pushup(p);
}
int ask1(int p,int l,int r){
if(t[p].l>=l&&t[p].r<=r) return t[p].val;
pushdown(p);
int mid=(t[p].l+t[p].r)>>1,ans=0;
if(l<=mid) ans+=ask1(ls(p),l,r);
if(r>mid) ans+=ask1(rs(p),l,r);
pushup(p);
return ans;
}
int ask0(int p,int l,int r){
if(t[p].l>=l&&t[p].r<=r) return t[p].r-t[p].l+1-t[p].val;
pushdown(p);
int mid=(t[p].l+t[p].r)>>1,ans=0;
if(l<=mid) ans+=ask0(ls(p),l,r);
if(r>mid) ans+=ask0(rs(p),l,r);
pushup(p);
return ans;
}
inline void work1(int x,int y,int opt){
int ans=ask1(1,a[x].id,a[x].id+a[x].size-1);
change(1,a[x].id,a[x].id+a[x].size-1,opt);
printf("%d
",ans);
}
inline void work0(int x,int y,int opt){
int ans=0;
while(a[x].top!=a[y].top){
if(a[a[x].top].dep<a[a[y].top].dep) swap(x,y);
ans+=ask0(1,a[a[x].top].id,a[x].id);
change(1,a[a[x].top].id,a[x].id,opt);x=a[a[x].top].fa;
}
if(a[x].dep>a[y].dep) swap(x,y);
ans+=ask0(1,a[x].id,a[y].id);change(1,a[x].id,a[y].id,opt);
printf("%d
",ans);
}
int main(){
n=read();
for(int i=2;i<=n;i++){int x=read()+1;add(x,i);}
m=read();
dfs1(1,0);dfs2(1,1);build(1,1,n);
for(int i=1;i<=m;i++){
string s;cin>>s;int x=read()+1;
if(s[0]=='u') work1(x,1,0);
else if(s[0]=='i') work0(x,1,1);
}
return 0;
}