[NOI2015]软件包管理器(树链剖分)

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define ll long long
  5 using namespace std;
  6 const ll maxn=1e5+10;
  7 ll n,m,cnt,head[maxn],nod,size[maxn],pre[maxn],wson[maxn],dfn[maxn],d[maxn],fa[maxn],tp,sum[maxn<<2],lazy[maxn<<2],a[maxn];
  8 ll top[maxn];
  9 char s[maxn];
 10 struct Edge{
 11     ll v,nxt;
 12 }E[maxn<<1];
 13 inline ll read()
 14 {
 15     ll x=0,f=1;char c=getchar();
 16     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
 17     while(c>=‘0‘&&c<=‘9‘){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
 18     return x*f;
 19 }
 20 inline ll max(ll a,ll b)
 21 {
 22     return a>b?a:b;
 23 }
 24 inline void addedge(ll u,ll v)
 25 {
 26     E[++cnt].v=v;
 27     E[cnt].nxt=head[u];
 28     head[u]=cnt;
 29 }
 30 inline void dfs1(ll u,ll f)
 31 {
 32     size[u]=1;d[u]=d[f]+1;
 33     for(ll i=head[u];i;i=E[i].nxt)
 34     {
 35         ll v=E[i].v;
 36         if(v==f)continue;
 37         dfs1(v,u);
 38         fa[v]=u;
 39         size[u]+=size[v];
 40         if(size[wson[u]]<size[v])wson[u]=v;
 41     }
 42 }
 43 inline void dfs2(ll u,ll tp)
 44 {
 45     top[u]=tp;dfn[u]=++nod;pre[nod]=u;
 46     if(wson[u])dfs2(wson[u],tp);
 47     for(ll i=head[u];i;i=E[i].nxt)
 48     {
 49         ll v=E[i].v;
 50         if(v==fa[u]||v==wson[u])continue;
 51         dfs2(v,v);
 52     }
 53 }
 54 inline void pushup(ll k){sum[k]=sum[k<<1]+sum[k<<1|1];}
 55 inline void pushdown(ll k,ll l,ll r)
 56 {
 57     ll mid=l+r>>1;
 58     lazy[k<<1]=lazy[k];lazy[k<<1|1]=lazy[k];
 59     sum[k<<1]=(mid-l+1)*max(lazy[k],0);sum[k<<1|1]=(r-mid)*max(lazy[k],0);
 60     lazy[k]=0;
 61 }
 62 inline void update(ll k,ll l,ll r,ll ql,ll qr,ll v)
 63 {
 64     ll mid=l+r>>1;
 65     if(l==ql&&r==qr){sum[k]=(qr-ql+1)*v;lazy[k]=(v==1?1:-1);return;}
 66     if(lazy[k]!=0)pushdown(k,l,r);
 67     if(qr<=mid)update(k<<1,l,mid,ql,qr,v);
 68     else if(ql>=mid+1)update(k<<1|1,mid+1,r,ql,qr,v);
 69     else update(k<<1,l,mid,ql,mid,v),update(k<<1|1,mid+1,r,mid+1,qr,v);
 70     pushup(k);
 71 }
 72 inline ll query_sum(ll k,ll l,ll r,ll ql,ll qr)
 73 {
 74     ll mid=l+r>>1;
 75     if(l==ql&&r==qr)return sum[k];
 76     if(lazy[k]!=0)pushdown(k,l,r);
 77     if(qr<=mid)return query_sum(k<<1,l,mid,ql,qr);
 78     else if(ql>=mid+1)return query_sum(k<<1|1,mid+1,r,ql,qr);
 79     else return query_sum(k<<1,l,mid,ql,mid)+query_sum(k<<1|1,mid+1,r,mid+1,qr);
 80     pushup(k);
 81 }
 82 inline ll install(ll x)
 83 {
 84     ll ans=0,tmp=x;
 85     while(top[x]!=top[1])
 86     {
 87         ans+=query_sum(1,1,n,dfn[top[x]],dfn[x]);
 88         update(1,1,n,dfn[top[x]],dfn[x],1);
 89         x=fa[top[x]];
 90     }
 91     ans+=query_sum(1,1,n,dfn[1],dfn[x]);
 92     update(1,1,n,dfn[1],dfn[x],1);
 93     return d[tmp]-ans;
 94 }
 95 inline ll uninstall(ll x)
 96 {
 97     ll ans=query_sum(1,1,n,dfn[x],dfn[x]+size[x]-1);
 98     update(1,1,n,dfn[x],dfn[x]+size[x]-1,0);
 99     return ans;
100 }
101 int main()
102 {
103 //    freopen("data.in","r",stdin);
104 //    freopen("my.out","w",stdout);
105     n=read();
106     for(ll i=2;i<=n;++i)
107     {
108         ll a=read()+1;
109         addedge(a,i);addedge(i,a);
110     }
111     m=read();
112     dfs1(1,0);dfs2(1,1);
113     for(ll i=1;i<=m;++i)
114     {
115         ll x;
116         scanf("%s",s+1);x=read()+1;
117         if(s[1]==‘i‘)printf("%lld\n",install(x));
118         else if(s[1]==‘u‘)printf("%lld\n",uninstall(x));
119     }
120     return 0;
121 }