第一个数据点都没办法完全读入,看不出来哪里写挂了,有没有dalao帮忙看看( 下面是代码
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x,f;char ch;
for(f=0;!isdigit(ch=getchar());f=ch=='-');
for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
return f?-x:x;
}
int rs;
struct edge {
int to;edge* gone;
}rd[200001];
edge *head[100001];
struct node {
long long value;
int dfn,top,dad,wson,size,deep;
}nd[100001];
int cnt,pre[100001];
int n=read();
inline void dfs1(int x,int dep) {
nd[x].deep=dep;nd[x].size=1;
for(edge *i=head[x];i!=NULL;i=i->gone) {
int nex=i->to;
if(nd[nex].deep) continue;
nd[nex].dad=x;
dfs1(nex,dep+1);
nd[x].size+=nd[nex].size;
if(nd[nex].size>nd[nd[x].wson].size) nd[x].wson=nex;
}
return ;
}
inline void dfs2(int x,int tp) {
nd[x].top=tp;nd[x].dfn=++cnt;
if(nd[x].wson) dfs2(nd[x].wson,tp);
for(edge *i=head[x];i!=NULL;i=i->gone) {
int nex=i->to;
if(nd[nex].deep<nd[x].deep || nex==nd[x].wson) continue;
dfs2(nex,nex);
}
return ;
}
struct litree {
int sum[200001],lazy[200001];
int ss,lson[200001],rson[200001];
inline void pushup(int x) { sum[x]=(sum[lson[x]]+sum[rson[x]]); }
inline void lazy_add(int x,int l,int r) {
if(lazy[x]==1) {
int mid=(l+r)>>1;
sum[lson[x]]=mid-l+1;
sum[rson[x]]=r-mid;
lazy[lson[x]]=1;
lazy[rson[x]]=1;
lazy[x]=0;
}else {
sum[lson[x]]=0;
sum[rson[x]]=0;
lazy[lson[x]]=-1;
lazy[rson[x]]=-1;
lazy[x]=0;
}
return ;
}
inline void build (int x,int l,int r) {
ss++;
if(l==r) {
sum[x]=0;
return ;
}
int mid=(l+r)>>1;
lson[x]=ss+1;
build(ss+1,l,mid);
rson[x]=ss+1;
build(ss+1,mid+1,r);
pushup(x);
return ;
}
inline void add(int x,int l,int r,int L,int R,int z) {
if(l>R || r<L) return ;
if(l>=L && r<=R) {
if(z==1) sum[x]=r-l+1;
else sum[x]=0;
lazy[x]=z;
return ;
}
if(lazy[x]) lazy_add(x,l,r);
int mid=(l+r)>>1;
add(lson[x],l,mid,L,R,z);
add(rson[x],mid+1,r,L,R,z);
pushup(x);
return ;
}
inline int check(int x,int l,int r,int L,int R) {
if(l>R || r<L) return 0;
if(l>=L && r<=R) {
return sum[x];
}
if(lazy[x]) lazy_add(x,l,r);
int mid=(l+r)>>1;
int k=(check(lson[x],l,mid,L,R)+check(rson[x],mid+1,r,L,R));
pushup(x);
return k;
}
}tree;
inline void ins(int x) {
int sum=0,al=0;
while(nd[x].top!=1) {
al+=nd[x].dfn-nd[nd[x].top].dfn+1;
sum+=tree.check(1,1,n,nd[nd[x].top].dfn,nd[x].dfn);
tree.add(1,1,n,nd[nd[x].top].dfn,nd[x].dfn,1);
x=nd[nd[x].top].dad;
}
al+=nd[x].dfn-nd[nd[x].top].dfn+1;
sum+=tree.check(1,1,n,nd[nd[x].top].dfn,nd[x].dfn);
tree.add(1,1,n,nd[nd[x].top].dfn,nd[x].dfn,1);
printf("%d\n",al-sum);
}
inline void uni(int x) {
int sum=0;
sum=tree.check(1,1,n,nd[x].dfn,nd[x].dfn+nd[x].size-1);
tree.add(1,1,n,nd[x].dfn,nd[x].dfn+nd[x].size-1,-1);
printf("%d\n",sum);
}
int main() {
for(int i=2;i<=n;i++) {
int x=read()+1;
rd[rs].to=i;rd[rs].gone=head[x];
head[x]=&rd[rs++];
}
dfs1(1,1);
dfs2(1,1);
tree.build(1,1,n);
int q=read();
for(int i=1;i<=q;i++) {
char k=getchar();int x=read()+1;
if(k=='i') {
ins(x);
}else {
uni(x);
}
}
return 0;
}