Dispatching

3.cpp

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

#define endl '\n'
#define MP make_pair
#define int long long
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define ar array
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

const int max_n = 3e5 + 10;
const ll mod = 1e9 + 7;
const ll M = 1e9;
const ll inf = 1e9;
const ld eps = 1e-9;

void setio(string name = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if (!name.empty()) {
    freopen((name + ".txt").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  } else {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
  }
}
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
int hdx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
int hdy[] = {-2, -1, 1, 2, 2, 1, -1, -2};
bool inside(int x, int y, int n, int m) {
  return x >= 0 && x < n && y >= 0 && y < m;
}

vector<int> adj[max_n];
vector<int> level(max_n, 1), salary(max_n, 0);
vector<int> sum(max_n, 0);
int n, m, res = 0LL;
priority_queue<int> pq[max_n];

void dfs(int v) {
  pq[v].push(salary[v]);
  sum[v] += salary[v];
  for (int u : adj[v]) {
    dfs(u);
    if (pq[u].size() > pq[v].size()) {
      swap(pq[u], pq[v]);
    }
    while (pq[u].size() > 0) {
      pq[v].push(pq[u].top());
      pq[u].pop();
    }
    sum[v] += sum[u];
  }
  while (m < sum[v]) {
    sum[v] -= pq[v].top();
    pq[v].pop();
  }
  res = max(res, level[v] * (int)pq[v].size());
}

void solve() {
  cin >> n;
  cin >> m;
  int root = 1;
  for (int i = 1; i <= n; i++) {
    int p, s, l;
    cin >> p >> s >> l;
    if (p == 0)
      root = i;
    else
      adj[p].push_back(i);
    salary[i] = s;
    level[i] = l;
  }
  dfs(root);
  cout << res << endl;
}

int32_t main() {
  setio();
  int tc = 1;
  auto start_time = clock();
  // cin >> tc;
  for (int t = 1; t <= tc; t++) {
    // cout << "case #" << t << ": ";
    solve();
  }
  auto end_time = clock();
#ifndef ONLINE_JUDGE
  cout << "Time taken:" << (double)(end_time - start_time) / CLOCKS_PER_SEC
       << "s" << endl;
#endif
  return 0;
}