solution-code4469

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
using namespace std;
6
struct Node
7
{
8
  int to,next;
9
}e[200005];
10
struct Tree
11
{
12
  int L,R,lazy,sum;
13
}T[400005];
14
int siz[200005],d[200005],h[200005],pre[200005],vson[200005],pos[200005],top[200005],sign,cnt;
15
inline void Addedge(int x,int y)
16
{
17
  e[++cnt]=(Node){y,h[x]};h[x]=cnt;return;
18
}
19
inline void dfs1(int x,int dep)
20
{
21
  int i,y;
22
  d[x]=dep;siz[x]=1;
23
  vson[x]=-1;
24
  for(i=h[x];i;i=e[i].next)
25
  {
26
    y=e[i].to;
27
    dfs1(y,dep+1);
28
    siz[x]+=siz[y];
29
    if(vson[x]==-1||siz[vson[x]]<siz[y])vson[x]=y;
30
  }
31
  return;
32
}
33
inline void dfs2(int x,int sp)
34
{
35
  int i,y;
36
  pos[x]=++sign;top[x]=sp;
37
  if(vson[x]!=-1)dfs2(vson[x],sp);
38
  for(i=h[x];i;i=e[i].next)
39
  {
40
    y=e[i].to;
41
    if(y==vson[x])continue;
42
    dfs2(y,y);
43
  }
44
  return;
45
}
46
inline void Build(int L,int R,int v)
47
{
48
  T[v].L=L;T[v].R=R;
49
  T[v].lazy=-1;
50
  if(L==R)return;
51
  int mid=(L+R)>>1;
52
  Build(L,mid,v<<1);
53
  Build(mid+1,R,(v<<1)|1);
54
  return;
55
}
56
inline void pushdown(int v)
57
{
58
  if(T[v].lazy==-1)return;
59
  T[v<<1].sum=(T[v<<1].R-T[v<<1].L+1)*T[v].lazy;
60
  T[(v<<1)|1].sum=(T[(v<<1)|1].R-T[(v<<1)|1].L+1)*T[v].lazy;
61
  T[v<<1].lazy=T[(v<<1)|1].lazy=T[v].lazy;
62
  T[v].lazy=-1;
63
  return;
64
}
65
inline void pushup(int v)
66
{
67
  T[v].sum=T[v<<1].sum+T[(v<<1)|1].sum;
68
  return;
69
}
70
inline void Insert(int L,int R,int val,int v)
71
{
72
  if(L>T[v].R||R<T[v].L)return;
73
  if(L<=T[v].L&&R>=T[v].R)
74
  {
75
    T[v].sum=(T[v].R-T[v].L+1)*val;
76
    T[v].lazy=val;return;
77
  }
78
  pushdown(v);
79
  Insert(L,R,val,v<<1);
80
  Insert(L,R,val,(v<<1)|1);
81
  pushup(v);
82
  return;
83
}
84
inline void Insert(int x,int y,int val)
85
{
86
  while(top[x]!=top[y])
87
  {
88
    if(d[top[x]]<d[top[y]])swap(x,y);
89
    Insert(pos[top[x]],pos[x],val,1);
90
    x=pre[top[x]];
91
  }
92
  if(d[x]>d[y])swap(x,y);
93
  Insert(pos[x],pos[y],val,1);
94
  return;
95
}
96
char cmd[15];
97
int main(void)
98
{
99
  int i,n,m,x,lst;
100
  scanf("%d",&n);
101
  for(i=2;i<=n;++i)
102
  {
103
    scanf("%d",&pre[i]);++pre[i];
104
    Addedge(pre[i],i);
105
  }
106
  dfs1(1,1);
107
  dfs2(1,1);
108
  Build(1,sign,1);
109
  scanf("%d",&m);
110
  for(i=1;i<=m;++i)
111
  {
112
    scanf("%s%d",cmd,&x);++x;
113
    lst=T[1].sum;
114
    if(strcmp(cmd,"install")==0)
115
    {
116
      Insert(1,x,1);
117
      printf("%d\n",T[1].sum-lst);
118
    }
119
    else
120
    {
121
      Insert(pos[x],pos[x]+siz[x]-1,0,1);
122
      printf("%d\n",lst-T[1].sum);
123
    }
124
  }
125
  return 0;
126
}