- #include
- #include
- #include
- #include
- using namespace std;
- int
- k=
- 0
- ,siz[
- 100101
- ],fa[
- 100101
- ],dep[
- 100101
- ],top[
- 100101
- ],son[
- 100101
- ],dfs[
- 100101
- ],dfn=
- 0;
- int
- h[
- 100101
- ],nxt[
- 200101
- ],to[
- 200101];
- int
- sum[
- 400000
- ],l[
- 400000
- ],r[
- 400000
- ],lazy[
- 400000];
- void
- ins(
- int
- u,
- int
- v){nxt[++k]=h[u];to[k]=v;h[u]=
- k;}
- void
- dfs1(
- int
- x,
- int
- f,
- int d)
- {
- fa[x]
- =f;siz[x]=
- 1
- ;dep[x]=
- d;
- for
- (
- int
- i=h[x];i;i=
- nxt[i])
- {
- int
- y=to[i];
- if
- (y==f)
- continue;
- dfs1(y,x,d
- +
- 1
- );siz[x]+=
- siz[y];
- if
- (son[x]==
- 0
- ||siz[y]>siz[son[x]])son[x]=
- y;
- }
- }
- void
- dfs2(
- int
- x,
- int t)
- {
- top[x]
- =t;dfs[x]=++
- dfn;
- if(son[x])dfs2(son[x],t);
- for
- (
- int
- i=h[x];i;i=
- nxt[i])
- {
- int
- y=to[i];
- if
- (y==fa[x]||y==son[x])
- continue;
- dfs2(y,y);
- }
- }
- void
- pushup(
- int x)
- {
- sum[x]
- =sum[x<<
- 1
- ]+sum[x<<
- 1
- |
- 1];
- }
- void
- pushdown(
- int x)
- {
- if
- (lazy[x]==-
- 1
- )
- return;
- lazy[x
- <<
- 1
- ]=
- lazy[x];
- lazy[x
- <<
- 1
- |
- 1
- ]=
- lazy[x];
- sum[x
- <<
- 1
- ]=lazy[x]*(r[x<<
- 1
- ]-l[x<<
- 1
- ]+
- 1);
- sum[x
- <<
- 1
- |
- 1
- ]=lazy[x]*(r[x<<
- 1
- |
- 1
- ]-l[x<<
- 1
- |
- 1
- ]+
- 1);
- lazy[x]
- =-
- 1;
- }
- void
- add(
- int
- x,
- int
- L,
- int
- R,
- int k)
- {
- if
- (L==l[x]&&R==r[x]){lazy[x]=k;sum[x]=lazy[x]*(r[x]-l[x]+
- 1
- );
- return;}
- pushdown(x);
- int
- mid=(l[x]+r[x])>>
- 1;
- if
- (R<=mid)add(x<<
- 1,L,R,k);
- else if
- (L>mid)add(x<<
- 1
- |
- 1,L,R,k);
- else
- {add(x<<
- 1
- ,L,mid,k);add(x<<
- 1
- |
- 1
- ,mid+
- 1,R,k);}
- pushup(x);
- }
- void
- query(
- int
- x,
- int
- L,
- int
- R,
- int
- k,
- int
- &
- ans)
- {
- if
- (L==l[x]&&R==
- r[x])
- {
- if
- (k)ans+=(r[x]-l[x]+
- 1
- )-
- sum[x];
- else
- ans+=sum[x];
- return;
- }
- pushdown(x);
- int
- mid=(l[x]+r[x])>>
- 1;
- if
- (R<=mid)query(x<<
- 1,L,R,k,ans);
- else if
- (L>mid)query(x<<
- 1
- |
- 1,L,R,k,ans);
- else
- {query(x<<
- 1
- ,L,mid,k,ans);query(x<<
- 1
- |
- 1
- ,mid+
- 1,R,k,ans);}
- }
- void
- init(
- int
- x,
- int
- L,
- int R)
- {
- l[x]
- =L;r[x]=R;lazy[x]=-
- 1
- ;
- if
- (L==R)
- return;
- int
- mid=(L+R)>>
- 1;
- init(x
- <<
- 1
- ,L,mid);init(x<<
- 1
- |
- 1
- ,mid+
- 1,R);
- }
- int main()
- {
- int
- n;scanf(
- "%d"
- ,&
- n);
- for
- (
- int
- i=
- 1
- ;i
- )
- {
- int
- v;scanf(
- "%d"
- ,&
- v);
- ins(i,v);ins(v,i);
- }
- dfs1(0
- ,
- 0
- ,
- 1
- );dfs2(
- 0
- ,
- 0);
- int
- m;scanf(
- "%d"
- ,&
- m);
- init(1
- ,
- 1,n);
- for
- (
- int
- i=
- 1
- ;i<=m;i++
- )
- {
- char
- c[
- 100
- ];
- int
- x;scanf(
- "%s%d"
- ,c,&
- x);
- if
- (c[
- 0
- ]==
- 'i')
- {
- int
- _ans=
- 0
- ,ans=
- 0;
- while
- (top[x]!=
- 0)
- {
- query(1
- ,dfs[top[x]],dfs[x],
- 1
- ,ans);_ans+=ans;ans=
- 0;
- add(1
- ,dfs[top[x]],dfs[x],
- 1
- );x=
- fa[top[x]];
- }
- query(1
- ,dfs[top[x]],dfs[x],
- 1
- ,ans);_ans+=
- ans;
- add(1
- ,dfs[top[x]],dfs[x],
- 1);
- printf("%d\n",_ans);
- }
- else
- {
- int
- _ans=
- 0
- ,ans=
- 0;
- query(1
- ,dfs[x],dfs[x]+siz[x]-
- 1
- ,
- 0
- ,ans);_ans+=
- ans;
- add(1
- ,dfs[x],dfs[x]+siz[x]-
- 1
- ,
- 0);
- printf("%d\n",_ans);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2159830.html