计蒜客 - 青出于蓝胜于蓝

#include<bits/stdc++.h>
using namespace std;

const int maxn=100000+100;
struct Edge{
  
  int to,next;
}edge[maxn<<1];
int head[maxn],tot;
int Id[maxn],Rev[maxn],Max[maxn],id;
struct Tree{
  
  int sum;
  int l,r;
}tree[maxn*20];
int root[maxn],num;
int key;

void DFS(int u,int fa){
  
  Id[u]= ++id;
  Max[u]=id;
  Rev[id]=u;
  for(int i=head[u];i!=-1;i=edge[i].next){
    
    Edge e=edge[i];
    int v=e.to;
    if(v==fa) continue;
    DFS(v,u);
    Max[u]=max(Max[u],Max[v]);
  }
}

void build(int &x,int l,int r){
  
  x= ++num;
  tree[x].sum=0;
  if(l==r) return ;
  int mid=(l+r)>>1;
  build(tree[x].l,l,mid);
  build(tree[x].r,mid+1,r);
}

inline void update(int &x,int old,int l,int r,int ind){
  
  x= ++num;
  tree[x]=tree[old];
  tree[x].sum=tree[old].sum+1;
  if(l==r) return ;
  int mid=(l+r)>>1;
  if(mid>=ind) update(tree[x].l,tree[old].l,l,mid,ind);
  else update(tree[x].r,tree[old].r,mid+1,r,ind);
}

inline void query(int ltree,int rtree,int l,int r,int v){
  
  if(l==r) return ;
  int cnt=tree[tree[rtree].l].sum-tree[tree[ltree].l].sum;
  int mid=(l+r)>>1;
  if(mid>=v) query(tree[ltree].l,tree[rtree].l,l,mid,v);
  else key+=cnt,query(tree[ltree].r,tree[rtree].r,mid+1,r,v);
}

int main(){
  
  int n,rt;
  scanf("%d%d",&n,&rt);
  for(int i=1;i<=n;i++) head[i]=-1;
  tot=0;
  for(int i=1;i<n;i++){
    
    int u,v;
    scanf("%d%d",&u,&v);
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
    edge[tot].to=u;
    edge[tot].next=head[v];
    head[v]=tot++;
  }
  DFS(rt,-1);
  num=0;
  build(root[0],1,n);
  for(int i=1;i<=n;i++) update(root[i],root[i-1],1,n,Rev[i]);
  for(int i=1;i<=n;i++){
    
    key=0;
    query(root[Id[i]-1],root[Max[i]],1,n,i);
    printf("%d%c",key,i==n?'\n':' ');
  }
}