bzoj 2809: [Apio2012]dispatching

    
    
    
    

     
     
     
     
 
      #include<cstdio> 
     
     
     
     
     
 
      #include<cstdlib> 
     
     
     
     
     
 
      #include<cstring> 
     
     
     
     
     
 
      #include<algorithm> 
     
     
     
     
     
 
        
     
     
     
     
     
 
      #define ll long long 
     
     
     
     
     
 
      #define inf 1e9 
     
     
     
     
     
 
      #define eps 1e-8 
     
     
     
     
     
 
      #define md 
     
     
     
     
     
 
      #define N 100010 
     
     
     
     
     
 
      #define TR 3200010 
     
     
     
     
     
 
      using namespace std; 
     
     
     
     
     
 
      struct yts { int x,t,ne;} e[N]; 
     
     
     
     
     
 
      int v[N],root[N],C[N]; 
     
     
     
     
     
 
      int sz[TR],ch[TR][2]; 
     
     
     
     
     
 
      ll sum[TR],L[N]; 
     
     
     
     
     
 
      int cnt,m,num; 
     
     
     
     
     
 
      ll ans=0; 
     
     
     
     
     
 
      void put(int x,int y) 
     
     
     
     
     
 
      { 
     
     
     
     
     
 
       num++; e[num].x=x; e[num].t=y; 
     
     
     
     
     
 
       e[num].ne=v[x]; v[x]=num; 
     
     
     
     
     
 
      } 
     
     
     
     
     
 
        
     
     
     
     
     
 
      int query(int i,int l,int r,int s) 
     
     
     
     
     
 
      { 
     
     
     
     
     
 
       if (sum[i]<=s) return sz[i]; 
     
     
     
     
     
 
       if (l==r) return s/l; 
     
     
     
     
     
 
       int mid=(l+r)>>1; 
     
     
     
     
     
 
       if (sum[ch[i][0]]>=s) return query(ch[i][0],l,mid,s);  
     
     
     
     
     
 
       else return sz[ch[i][0]]+query(ch[i][1],mid+1,r,s-sum[ch[i][0]]); 
     
     
     
     
     
 
      } 
     
     
     
     
     
 
        
     
     
     
     
     
 
      void insert(int &i,int l,int r,int x) 
     
     
     
     
     
 
      { 
     
     
     
     
     
 
       i=++cnt; sz[i]=1; sum[i]=x; 
     
     
     
     
     
 
       if (l==r) return; 
     
     
     
     
     
 
       int mid=(l+r)>>1; 
     
     
     
     
     
 
       if (x<=mid) insert(ch[i][0],l,mid,x); 
     
     
     
     
     
 
       else insert(ch[i][1],mid+1,r,x); 
     
     
     
     
     
 
      } 
     
     
     
     
     
 
        
     
     
     
     
     
 
      int merge(int x,int y) 
     
     
     
     
     
 
      { 
     
     
     
     
     
 
       if (!x) return y; 
     
     
     
     
     
 
       if (!y) return x; 
     
     
     
     
     
 
       sz[x]+=sz[y]; sum[x]+=sum[y]; 
     
     
     
     
     
 
       ch[x][0]=merge(ch[x][0],ch[y][0]); 
     
     
     
     
     
 
       ch[x][1]=merge(ch[x][1],ch[y][1]); 
     
     
     
     
     
 
       return x; 
     
     
     
     
     
 
      } 
     
     
     
     
     
 
        
     
     
     
     
     
 
      void outit(int x) 
     
     
     
     
     
 
      { 
     
     
     
     
     
 
       printf("%d : %d %lld
",x,sz[x],sum[x]); 
     
     
     
     
     
 
       if (ch[x][0]) outit(ch[x][0]); 
     
     
     
     
     
 
       if (ch[x][1]) outit(ch[x][1]); 
     
     
     
     
     
 
      } 
     
     
     
     
     
 
        
     
     
     
     
     
 
      void dfs(int x) 
     
     
     
     
     
 
      { 
     
     
     
     
     
 
       insert(root[x],1,m,C[x]); 
     
     
     
     
     
 
       for (int i=v[x];i;i=e[i].ne) 
     
     
     
     
     
 
       { 
     
     
     
     
     
 
       dfs(e[i].t); 
     
     
     
     
     
 
       root[x]=merge(root[x],root[e[i].t]); 
     
     
     
     
     
 
       } 
     
     
     
     
     
 
       //outit(root[x]); printf("
"); 
     
     
     
     
     
 
       ll sz=query(root[x],1,m,m); 
     
     
     
     
     
 
       ans=max(ans,sz*L[x]); 
     
     
     
     
     
 
      } 
     
     
     
     
     
 
        
     
     
     
     
     
 
      int main() 
     
     
     
     
     
 
      { 
     
     
     
     
     
 
       //freopen("data.in","r",stdin); freopen("b.out","w",stdout); 
     
     
     
     
     
 
       int n,rt; 
     
     
     
     
     
 
       scanf("%d%d",&n,&m); 
     
     
     
     
     
 
       for (int i=1;i<=n;i++) 
     
     
     
     
     
 
       { 
     
     
     
     
     
 
       int fa; 
     
     
     
     
     
 
       scanf("%d%d%lld",&fa,&C[i],&L[i]); 
     
     
     
     
     
 
       if (fa) put(fa,i); else rt=i; 
     
     
     
     
     
 
       } 
     
     
     
     
     
 
       dfs(rt); 
     
     
     
     
     
 
       printf("%lld
",ans); 
     
     
     
     
     
 
       return 0; 
     
     
     
     
     
 
      }