记录编号	393224	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2012] 派遣	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.629 s
提交时间	2017-04-10 11:01:31	内存使用	5.65 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;
__gnu_pbds::priority_queue<int, less<int>, __gnu_pbds::pairing_heap_tag> pq[MAXN];
int lead[MAXN], fa[MAXN], money[MAXN], first[MAXN];
LL tot[MAXN], num[MAXN];
int size, n, m;
LL ans;
vector<int> G[MAXN];
void dfs(int u){
  if(money[u] < m)ans = max(ans, (LL)lead[u]);
  for(int i = 0; i < G[u].size(); i++){
    int to = G[u][i]; if(to == fa[u])continue;
    dfs(to);
    pq[u].join(pq[to]);
    num[u] += num[to];
    tot[u] += tot[to];
  }
  while(num[u] > m){
    num[u] -= pq[u].top();
    tot[u]--;
    pq[u].pop();
  }
  ans = max(ans, tot[u]*lead[u]);
}
int main(){
  freopen("dispatching.in", "r", stdin);
  freopen("dispatching.out", "w", stdout);
  scanf("%d %d", &n, &m);
  for(int i = 1; i <= n; i++){
    scanf("%d %d %d", fa+i, money+i, lead+i);
    G[i].push_back(fa[i]); G[fa[i]].push_back(i);
    pq[i].push(money[i]); tot[i] = 1; num[i] = money[i];
  }
  dfs(1);
  printf("%lld\n", ans);
  return 0;
}