【重链剖分】软件包管理器

题意： 有n个软件，每个软件的下载都可能依赖于最多一个其他的软件，当下载某一个软件的时候需要同时下载他所需要依赖的所有软件，同理删除这个软件的时候就需要删除依赖于他的所有软件。

分析：

1. 因为每一个软件都最多依赖于一个其他软件，即可转化为每一个软件最多有一个父亲，依赖关系=父子关系。
2. 那么要使能快速的求一个依赖于改软件的所有软件状态，就是求子树问题
3. 要快速能求一个软件依赖于哪些软件，实际上就是求一个软件的所有”父亲“
4. 根据2、3，要快速求得所有父亲和子树状态，可以使用树链剖分进行加速。 注意： 节点值更新的时候可以使用更新前的值减去更新后的值就是改变的值。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+12;
struct {
  int to,nex;
}edge[N];
int n,m,cnt,son[N],fa[N],head[N],sum[N],lazy[N],dep[N],siz[N];
int nu,id[N],w[N],top[N];
void addedge(int u,int v)
{
  edge[++cnt].to=v;
  edge[cnt].nex=head[u];
  head[u]=cnt;
}
void pushup(int x) { sum[x]=sum[x<<1]+sum[x<<1|1]; }
void pushdown(int x,int l,int r)
{
  if( lazy[x]==-1 ) return;
  //cout<<l<<" "<<r<<endl;
  if( lazy[x]==0 )
  {
    sum[x<<1]=sum[x<<1|1]=0;
    lazy[x<<1]=0,lazy[x<<1|1]=0;
  }
  else if( lazy[x]==1 )
  {
    int mid=l+r>>1;
    sum[x<<1]=mid-l+1,sum[x<<1|1]=r-mid;
    lazy[x<<1]=1,lazy[x<<1|1]=1;
  }
  lazy[x]=-1;
}
void update(int x,int l,int r,int L,int R,int v)
{
  if( L<=l and r<=R )
  {
  if(v) lazy[x]=1,sum[x]=(r-l+1);
  else lazy[x]=0,sum[x]=0;
  return;
  }
  pushdown(x,l,r);
  int mid=l+r>>1;
  if( L<=mid ) update( x<<1,l,mid,L,R,v);
  if( R>mid  ) update( x<<1|1,mid+1,r,L,R ,v);
  pushup(x);
}
int getsum( int x,int l,int r,int L,int R )
{
  //cout<<l<<" "<<r<<endl;
  if( L<=l and r<=R ) return sum[x];
  pushdown(x,l,r);
  int mid=l+r>>1;
  int ans=0;
  if( L<=mid ) ans+=getsum(x<<1,l,mid,L,R);
  if( R>mid  ) ans+=getsum(x<<1|1,mid+1,r,L,R);
  return ans;
}
void build(int x,int l,int r)
{
  int mid=l+r>>1;
  if(l==r) {lazy[x]=-1;return;}
  build(x<<1,l,mid);
  build(x<<1|1,mid+1,r);
}
void dfs1(int x,int f,int deep)
{
  dep[x]=deep;
  fa[x]=f;
  siz[x]=1;
  int maxson=0;
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( y==f ) continue;
    dfs1(y,x,deep+1);
    siz[x]+=siz[y];
    if( siz[y]>maxson )
      son[x]=y;maxson=siz[y];
  }
}
void dfs2(int x,int topf)
{
  id[x]=nu++;
  top[x]=topf;
  if( !son[x] ) return;
  dfs2(son[x],topf);
  for(int i=head[x];i;i=edge[i].nex)
  {
    int y=edge[i].to;
    if( y==fa[x] or y==son[x] ) continue;
    dfs2(y,y);
  }
}
void install(int x)
{
  while( top[x] )
  {
    update(1,0,n-1,id[top[x]],id[x],1);
    x=fa[top[x]];
  }
  //cout<<id[top[x]]<<" "<<id[x]<<endl;
  update(1,0,n-1,id[top[x]],id[x],1);
}
void unstall(int x)
{
  //cout<<id[x]<<" "<<id[x]+siz[x]-1<<endl;
  update(1,0,n-1,id[x],id[x]+siz[x]-1,0);
}
int qinstall(int x)
{
  int ans=0;
  while( top[x] )
  {
   // cout<<x<<" "<<id[x]<<" "<<id[top[x]]<<endl;
    ans+=(id[ x ]-id[ top[x] ] +1)-getsum(1,0,n-1,id[top[x]],id[x]);
    x=fa[top[x]];
  }
  //cout<<x<<" "<<id[x]<<" "<<id[top[x]]<<endl;
  ans+=( id[ x ]-id[ top[x] ] +1)-getsum(1,0,n-1,id[top[x]],id[x]);
  return ans;
}
int qunstall(int x)
{
  return getsum(1,0,n-1,id[x],id[x]+siz[x]-1);
}
int main(){
  //freopen("std.in","r",stdin);
  //freopen("std.out","w",stdout);
  cin>>n;
  int u,x;
  string s;
  for(int i=1;i<=n-1;i++)
  {
    cin>>u;
    addedge(i,u);
    addedge(u,i);
  }
  build(1,0,n-1);
  dfs1(0,0,1);
  dfs2(0,0);
  cin>>m;
  while(m--)
  {
    cin>>s>>x;
    if( s=="install" )
    {
      cout<<qinstall(x)<<endl;
      install(x);
    }
    else{
      cout<<qunstall(x)<<endl;
      unstall(x);
    }
    //for(int i=0;i<n;i++)
      //cout<<getsum(1,0,n-1,i,i)<<" ";
    //cout<<endl;

  }


}