제출 #840847

#제출 시각아이디문제언어결과실행 시간메모리
840847qthang2k11Magic Tree (CEOI19_magictree)C++17
100 / 100
94 ms30412 KiB
// https://codeforces.com/blog/entry/68748?#comment-530918
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 1e5 + 5;

int n, k, max_d, d[N], w[N];
vector<int> adj[N];

map<int, ll> dp[N];
int sz[N], id[N];

void insert(int x, int d, int w) {
  dp[x][d] += w;
  auto it = dp[x].upper_bound(d);
  while (it != dp[x].end() && it->second <= w)
    w -= it->second, it = dp[x].erase(it);
  if (it != dp[x].end()) it->second -= w;
}

void dfs(int x) {
  id[x] = x;
  sz[x] = d[x] > 0;
  int mx = -1, spec = x;
  for (int y: adj[x]) {
    dfs(y);
    if (sz[y] > mx)
      spec = y, mx = sz[y];
    sz[x] += sz[y];
  }
  id[x] = id[spec];
  for (int y: adj[x]) if (y != spec) {
    for (const auto &elem: dp[id[y]])
      dp[id[x]][elem.first] += elem.second;
    dp[id[y]].clear();
  }
  if (d[x]) insert(id[x], d[x], w[x]);
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k >> max_d;
  for (int i = 2; i <= n; i++) {
    int pi; 
    cin >> pi;
    adj[pi].emplace_back(i);
  }
  for (int i = 1, x; i <= k; i++)
    cin >> x >> d[x] >> w[x];
  dfs(1);
  ll ans = 0;
  for (const auto &elem: dp[id[1]])
    ans += elem.second;
  cout << ans;
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...