#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> d, w;
vector<vector<int>> gr;
vector<map<ll, ll>> chn;
void f(int node) {
auto &ret = chn[node];
for(auto y : gr[node]){
f(y);
if(ret.size() < chn[y].size())swap(ret, chn[y]);
for(auto x : chn[y])ret[x.first] += x.second;
}
if(w[node])ret[d[node]] += w[node];
ll am = w[node];
while(am) {
auto z = ret.upper_bound(d[node]);
if(z == ret.end())break;
ll mn = min(am, z->second);
z->second -= mn;
am -= mn;
if(!z->second)ret.erase(z);
}
}
int main () {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m, k; cin >> n >> m >> k;
gr.resize(n);
d.resize(n, 0);
w.resize(n, 0);
chn.resize(n);
for(int i = 1; i < n; ++i){
int p; cin >> p;
p--;
gr[p].push_back(i);
}
for(int i = 0; i < m; ++i){
int a, b, c; cin >> a >> b >> c;
a--;
d[a] = b;
w[a] = c;
}
f(0);
ll ans = 0;
for(auto x : chn[0])ans += x.second;
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |