给你一棵树，两个操作：
install x查询路径 \(0\to x\) 上的点权和，并将路径点权赋值为 \(1\)unistall x查询 \(x\) 的子树点权和，并将子树点权赋值为 \(0\)
板子。恶心。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+3;
int a[maxn],n,m;
vector<int>e[maxn];
void add_edge(int u,int v,bool type=1){
e[u].push_back(v);
if(type) e[v].push_back(u);//无向图
}
#define ls now<<1
#define rs now<<1|1
struct T{
int sum,tag;
}tree[maxn<<2];
void pushup(int now){
tree[now].sum=(tree[ls].sum+tree[rs].sum);
}
void pushdown(int now,int l,int r){
if(tree[now].tag==-1)return;
int mid=(l+r)>>1;
tree[ls].sum=tree[now].tag*(mid-l+1);
tree[rs].sum=tree[now].tag*(r-mid);
tree[ls].tag=tree[rs].tag=tree[now].tag;
tree[now].tag=-1;
}
void build(int now,int l,int r){
tree[now].tag=-1;
if(l==r){tree[now].sum=1;return;}
int mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
pushup(now);
}
void modify(int now,int l,int r,int x,int y,int v){
if(x<=l&&r<=y){
tree[now].sum=v*(r-l+1);
tree[now].tag=v;
return;
}
pushdown(now,l,r);
int mid=(l+r)>>1;
if(x<=mid)modify(ls,l,mid,x,y,v);
if(mid+1<=y)modify(rs,mid+1,r,x,y,v);
pushup(now);
}
int query(int now,int l,int r,int x,int y){
int ans=0;
if(x<=l&&r<=y)return tree[now].sum;
pushdown(now,l,r);
int mid=(l+r)>>1;
if(x<=mid)ans=(ans+query(ls,l,mid,x,y));
if(mid+1<=y)ans=(ans+query(rs,mid+1,r,x,y));
return ans;
}
int siz[maxn],dep[maxn],son[maxn],id[maxn],top[maxn],f[maxn],cnt;
void dfs1(int u,int fa,int depth){
siz[u]=1; f[u]=fa; dep[u]=depth;
int maxx=-maxn;
for(auto v:e[u]){
if(v!=fa){
dfs1(v,u,depth+1);
siz[u]+=siz[v];
if(siz[v]>maxx) maxx=siz[v],son[u]=v;
}
}
}
void dfs2(int u,int t){
id[u]=++cnt; top[u]=t;
if(!son[u]) return;
dfs2(son[u],t);
for(int v:e[u]) if(!id[v]) dfs2(v,v);
}
void modify_tree(int x,int y,int z){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
modify(1,1,n,id[top[x]],id[x],z);
x=f[top[x]];
}
if(id[x]>id[y])swap(x,y);
modify(1,1,n,id[x],id[y],z);
}
int query_tree(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=(ans+query(1,1,n,id[top[x]],id[x]));
x=f[top[x]];
}
if(id[x]>id[y])swap(x,y);
ans=(ans+query(1,1,n,id[x],id[y]));
return ans;
}
signed main(){
cin>>n;
for(int i=1,u;i<n;i++){
cin>>u;u++;
add_edge(i+1,u);
}
dfs1(1,1,1); dfs2(1,1);
build(1,1,n);
cin>>m;
string op;
for(int i=1,x,Ans;i<=m;i++){
cin>>op>>x;x++;
if(op=="install") cout<<query_tree(x,1)<<'\n',modify_tree(1,x,0);
else cout<<siz[x]-query(1,1,n,id[x],id[x]+siz[x]-1)<<'\n', modify(1,1,n,id[x],id[x]+siz[x]-1,1);
}
}