#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 int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int n,m,k; cin>>n>>m>>k; struct Fruit { int vertex, day, weight; }; vector<vector<int>> adj(n); vector<int> parent(n,0); parent[0]=0; for(int i=1; i<n; i++) { int par; cin>>par; par--; adj[par].push_back(i); adj[i].push_back(par); parent[i]=par; } vector<Fruit> fruits(m); for(int i=0; i<m; i++) { cin>>fruits[i].vertex>>fruits[i].day>>fruits[i].weight; } vector<pair<int, int>> fruit(n, {0, 0}); for(auto it: fruits) { fruit[it.vertex-1] = {it.day, it.weight}; } vector<pair<int, long long>> dp(n, {0,0}); vector<int> childCnt(n,0); for(int v=0; v<n; ++v){ childCnt[v] = (int)adj[v].size() - (v==0 ? 0 : 1); } vector<bool> visited(n, false); set<int> q; for(int i=1; i<n; i++) { if(childCnt[i]==0) { dp[i] = { fruit[i].first , (long long)fruit[i].second }; visited[i] = true; q.insert(parent[i]); } } while(!q.empty()) { int cur = *q.begin(); q.erase(q.begin()); vector<pair<int, long long>> children; for(int nb : adj[cur]) { if(visited[nb]) children.push_back(dp[nb]); } if(fruit[cur].first==0 && fruit[cur].second==0) { long long sum = 0; int 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<int,long long>& a, const pair<int,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; } int 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){ int 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; int p = parent[cur]; if(p != cur){ childCnt[p]--; if(childCnt[p]==0) q.insert(p); } } cout << dp[0].second << endl; }

magictree.cpp: In function 'int main()':
magictree.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~