%%%%
by Hexarhy @ 2019-04-04 21:32:38
顺带说一句，样例过不去
by Meatherm @ 2019-04-04 21:34:10
```cpp
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <ctype.h>
# include <iostream>
# include <cmath>
# include <map>
# include <vector>
# include <queue>
# define LL long long
# define ms(a,b) memset(a,b,sizeof(a))
# define ri (register int)
# define inf (0x7f7f7f7f)
# define pb push_back
# define fi first
# define se second
# define pii pair<int,int>
# define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
inline int gi(){
int w=0,x=0;char ch=0;
while(!isdigit(ch)) w|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
# define N 100005
struct segment_tree{
# define mid ((l+r)>>1)
# define ls (nod<<1)
# define rs (nod<<1|1)
struct node{
int l,r,s,tag;
}tr[N<<2];
void pushup(int nod){
tr[nod].s=tr[ls].s+tr[rs].s;
}
void pushdown(int nod){
int tmp=tr[nod].tag; tr[nod].tag=-1;
if (tmp==-1) return;
tr[ls].s=(tr[ls].r-tr[ls].l+1)*tmp;
tr[rs].s=(tr[rs].r-tr[rs].l+1)*tmp;
tr[ls].tag=tr[rs].tag=tmp;
}
void build(int l,int r,int nod){
tr[nod].l=l,tr[nod].r=r,tr[nod].tag=-1,tr[nod].s=0;
if (l>=r) return;
build(l,mid,ls); build(mid+1,r,rs);
pushup(nod);
}
void update_sec(int ql,int qr,int v,int nod){
int l=tr[nod].l,r=tr[nod].r;
if (ql<=l&&r<=qr){
tr[nod].tag=v;
tr[nod].s=(r-l+1)*v;
return;
}
pushdown(nod);
if (ql<=mid) update_sec(ql,qr,v,ls);
if (qr>mid) update_sec(ql,qr,v,rs);
pushup(nod);
}
}tr;
struct edge{
int to,nt;
}E[N<<1];
int son[N],top[N],sz[N],fa[N],H[N],dep[N],idx[N],pre[N];
int cnt,tot,n,m;
void addedge(int u,int v){
E[++cnt]=(edge){v,H[u]}; H[u]=cnt;
}
void dfs1(int u,int ft,int dp){
dep[u]=dp; fa[u]=ft; sz[u]=1;
int maxson=-1;
for (int e=H[u];e;e=E[e].nt){
int v=E[e].to; if (v==fa[u]) continue;
dfs1(v,u,dp+1); sz[u]+=sz[v];
if (sz[v]>maxson) maxson=sz[v],son[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp; idx[u]=++tot; pre[tot]=u;
if (!son[u]) return; dfs2(son[u],tp);
for (int e=H[u];e;e=E[e].nt){
int v=E[e].to; if (v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
void update(int u,int v,int w){
while (top[u]!=top[v]){
if (dep[top[u]]<dep[top[v]]) swap(u,v);
tr.update_sec(idx[top[u]],idx[u],w,1);
u=fa[top[u]];
}
if (dep[u]>dep[v]) swap(u,v);
tr.update_sec(idx[u],idx[v],w,1);
}
int main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
n=gi();
for (int i=2;i<=n;i++){
int u=gi();
addedge(u+1,i);
addedge(i,u+1);
}
m=gi();
dfs1(1,-1,1);
dfs2(1,1);
tr.build(1,n,1);
while (m--){
char opt[10];
scanf("%s",opt);
int t1=tr.tr[1].s,x=gi(); x++;
if (opt[0]=='i') update(1,x,1); else tr.update_sec(idx[x],idx[x]+sz[x]-1,0,1);
int t2=tr.tr[1].s;
printf("%d\n",abs(t1-t2));
}
return 0;
}
```
贡献蒟蒻代码
by mulberror @ 2019-04-04 21:41:53
@[兹磁洛谷](/space/show?uid=108949)
by mulberror @ 2019-04-04 21:42:00
~~去你的萌新~~
by Le_temps_des_fleurs @ 2019-04-04 21:56:19
Orz lzx&yjx
by F1aMiR3 @ 2019-04-04 22:09:22