「CEOI2019」魔法树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 100005;

vector<int> G[maxn];
map<int, ll> mp[maxn];
int d[maxn];
ll w[maxn];

int N, M, K;

void dfs(int u) {
    for (auto v: G[u]) {
        dfs(v);
        if (mp[u].size() < mp[v].size()) swap(mp[u], mp[v]);
        for (auto it: mp[v]) {
            mp[u][it.first] += it.second;
        }
    }
    if (d[u]) {
        mp[u][d[u]] += w[u];
        for (auto it = mp[u].upper_bound(d[u]); it != mp[u].end();) {
            if (it->second > w[u]) {
                it->second -= w[u];
                break;
            }
            w[u] -= it->second;
            it->second = 0;
            mp[u].erase(it++);
        }
    }
}

int main() {
    scanf("%d%d%d", &N, &M, &K);
    for (register int i = 2; i <= N; ++i) {
        int p;
        scanf("%d", &p);
        G[p].push_back(i);
    }
    for (register int i = 1; i <= M; ++i) {
        int v;
        scanf("%d", &v);
        scanf("%d%I64d", &d[v], &w[v]);
    }
    dfs(1);
    ll ans = 0;
    for (auto it: mp[1]) ans += it.second;
    printf("%I64d", ans);
    return 0;
}