Submission #840847

#	Time	Username	Problem	Language	Result	Execution time	Memory
840847		qthang2k11	Magic Tree (CEOI19_magictree)	C++17	100 / 100	94 ms	30412 KiB

magictree

// 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;
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 13 / 13
• Subtask 7: 22 / 22
• Subtask 8: 17 / 17