落谷　1552 [APIO2012]派遣

#include 
#include 
#include 
#include 
#include 
#include #define MAXN 200000
#define ll long long
using namespace std;
struct edge{
    int first;
    int next;
    int to;
}a[MAXN*2];
ll lll[MAXN],rf[MAXN],sum[MAXN],num[MAXN],c[MAXN],l[MAXN],dis[MAXN],r[MAXN];
int n,M;
ll ans=0,numm=0;

void addedge(int from,int to){
    a[++numm].to=to;
    a[numm].next=a[from].first;
    a[from].first=numm;
}

int merge(int x,int y){
    if(!x||!y) return x+y;
    if(c[x]c[y]) swap(x,y);
    r[x]=merge(r[x],y);
    if(dis[r[x]]>dis[l[x]]) swap(l[x],r[x]);
    dis[x]=dis[l[x]]+1;
    return x;
}

void dfs(int now){
    sum[now]=c[now],rf[now]=now,num[now]=1;
    for(int i=a[now].first;i;i=a[i].next){
        int to=a[i].to;
        dfs(to);
        sum[now]+=sum[to];
        num[now]+=num[to];
        rf[now]=merge(rf[now],rf[to]);
    }
    while(sum[now]>M){
        sum[now]-=c[rf[now]];
        rf[now]=merge(l[rf[now]],r[rf[now]]);
        num[now]--;
    }
    ans=max(ans,lll[now]*num[now]);
}

int main()
{
    scanf("%d%d",&n,&M);
    for(int i=1;i){
        ll x;
        scanf("%lld%lld%lld",&x,&c[i],&lll[i]);
        addedge(x,i);
    }
    dfs(1);
    printf("%lld",ans);
    return 0;
}