Submission #1317860

#TimeUsernameProblemLanguageResultExecution timeMemory
1317860thuhienneMagic Tree (CEOI19_magictree)C++20
34 / 100
2095 ms40280 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define re exit(0);

const int maxn = 100009;

int n,m,k;
vector <int> adj[maxn];

int day[maxn],fruit[maxn];

ll dp[maxn][29],prevdp[29];
//dp i j: xet den i, max canh noi voi i = j

void dfs(int node) {
	for (int child : adj[node]) {
		dfs(child);
		for (int i = 0;i <= k;i++) prevdp[i] = dp[node][i],dp[node][i] = 0;
		
		//duyet canh noi giua node va child
		for (int i = 1;i <= k;i++) {
			//duyet canh max noi voi child (phai nho hon bang i)
			for (int childmax = 0;childmax <= i;childmax++) {
				for (int prevmax = 0;prevmax <= k;prevmax++) {
					dp[node][max(prevmax,i)] = max(dp[node][max(prevmax,i)],prevdp[prevmax] + dp[child][childmax] + (i == day[child]) * fruit[child]);
				}
			}
		}
	
	}
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);

	cin >> n >> m >> k;
	for (int i = 2;i <= n;i++) {
		int p;cin >> p;
		adj[p].push_back(i);
	}
	
	for (int i = 1;i <= m;i++) {
		int ver;cin >> ver;
		cin >> day[ver] >> fruit[ver];
	}
	
	dfs(1);

	cout << *max_element(dp[1],dp[1] + k + 1);

}

/*
Aiming:
                                                           ==
                                                         +++++***
                                                        +:::::-=*
                                                         ------=
         ==========           ==================         --:--==              ============--
         ==========           ==-------=--:=--====       ---==++           ===========--====-=
        ==--========          ==--=================      =:::-=+          ==============----====
        ==:-=========         ===:===       =======      =::--=+         ========        ==--====
       ==--==========         ==-:===        =======     -:::-:=        =======           =======
      ==--:==  =======        ==--===        =======     =-:::-=        =======            =======
      =-.-===   =======       ==-====       =======     *:::----*       =======            =======
     ==--:==    =======       ==-==================     +-:::::-+       ======             =======
    ==-:-===     =======      ==--================     *=-:::::-=       =======            =======
    ==---===============      ==--=============        +--::---==*      ====--=            =======
   ===--=================     ==:-===                  =:-::::--=+      ====-===          =======
   ==.-===================    ==--===                  =::::::---+       ====---==      =========
  ==---==          =======    =======                 +-:---=====+        ==-===--==============
 =======            =======   =======                 =-:::::::--=+         =--=-=============
========             =======  =======                 =--::::::--=+           =============
                                                   ***++++++++++*****
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...