#include <bits/stdc++.h> using namespace std; // Let dp[i] be the {maximum answer, min day to obtain that answer} for a particular node i. // Initially for each leaf node, the answer is {0,0} if it does not have a fruit, else whatever the value of fruit it has. // Then, to calc the answer for a node i, // Sort the values of the dp for all it's children according to day. // Iterate through each child, and if the day is less than or equal to the parent's day, accumulate it to the parent node's magic, storing it in a var max_magic // The answer for that node is max(max_magic, sum of dp of all children) // Remember to update the day, and if there are many options, choose the earliest day using ll=long long; int main() { ll n,m,k; cin>>n>>m>>k; struct Fruit { ll vertex, day, weight; }; vector<vector<ll>> adj(n); vector<ll> parent(n,0); parent[0]=0; for(ll i=1; i<n; i++) { ll par; cin>>par; par--; adj[par].push_back(i); adj[i].push_back(par); parent[i]=par; } vector<Fruit> fruits(m); for(ll i=0; i<m; i++) { cin>>fruits[i].vertex>>fruits[i].day>>fruits[i].weight; } vector<pair<ll, ll>> fruit(n, {0, 0}); for(auto it: fruits) { fruit[it.vertex-1] = {it.day, it.weight}; } vector<pair<ll, long long>> dp(n, {0,0}); vector<ll> childCnt(n,0); for(ll v=0; v<n; ++v){ childCnt[v] = (ll)adj[v].size() - (v==0 ? 0 : 1); } vector<bool> visited(n, false); set<ll> q; for (ll i = 1; i < n; ++i) { if (childCnt[i] == 0) { dp[i] = { fruit[i].first , fruit[i].second }; visited[i] = true; ll p = parent[i]; if (p != i) { --childCnt[p]; if (childCnt[p] == 0) q.insert(p); } } } while(!q.empty()) { ll cur = *q.begin(); q.erase(q.begin()); vector<pair<ll, long long>> children; for(ll nb : adj[cur]) { if(visited[nb]) children.push_back(dp[nb]); } if(fruit[cur].first==0 && fruit[cur].second==0) { long long sum = 0; ll max_day = 0; for(auto &ch : children){ sum += ch.second; max_day = max(max_day, ch.first); } dp[cur] = { max_day , sum }; } else { sort(children.begin(), children.end(), [](const pair<ll,long long>& a, const pair<ll,long long>& b){ return a.first < b.first; }); long long max_magic = fruit[cur].second; long long sum = 0; for(auto &ch : children){ if(ch.first <= fruit[cur].first) max_magic += ch.second; sum += ch.second; } ll end_day = 0; if(!children.empty()) end_day = children.back().first; if(max_magic > sum){ dp[cur] = { max(end_day, fruit[cur].first) , max_magic }; } else if(sum > max_magic){ ll max_child_day = 0; for(auto &ch : children) max_child_day = max(max_child_day, ch.first); dp[cur] = { max_child_day , sum }; } else { dp[cur] = { min(end_day, fruit[cur].first) , sum }; } } visited[cur] = true; ll p = parent[cur]; if(p != cur){ childCnt[p]--; if(childCnt[p]==0) q.insert(p); } } cout << dp[0].second << endl; }