Laskettelukeskus

#include <bits/stdc++.h>

#define forn(i, n) for(int i=0; i<n; i++)
#define FOR(i, j, n) for(int i=j; i<n; i++)
#define pb push_back
#define F first
#define S second

typedef long long ll;

const int inf = 1.01e9;
const int mod = 1e9 + 7;

using namespace std;

int n;
int arr[100000];
int mem[100000];
vector<vector<int>> v;

ll haku(ll h);

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n;
	v.resize(n+1);
	int a, b;
	FOR(i, 1, n) {
		cin >> a >> b;
		v[a].pb(b);
	}
	
	FOR(i, 1, n+1) cin >> arr[i];
	
	cout << haku(1);
	
	return 0;
}

ll haku(ll h) {
	if (mem[h]) return mem[h]-1;
	ll summa = 0;
	
	for (int i : v[h]) {
		summa += haku(i);
	}
	// cout << h << " " << summa << "\n";
	mem[h] = max(summa, (ll)arr[h]) + 1;
	return max(summa, (ll)arr[h]);
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 5

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 1, 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED