제출 #933048

#제출 시각아이디문제언어결과실행 시간메모리
933048Cyber_WolfMagic Tree (CEOI19_magictree)C++17
100 / 100
77 ms30548 KiB
#include <bits/stdc++.h>

using namespace std;

#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg N = 1e5+5;

lg n, m, k;
lg v[N], d[N];
vector<lg> adj[N];
map<lg, lg> mp2;

void solve(lg src)
{
	map<lg, lg> mp;
	for(auto it : adj[src])
	{
		solve(it);
		if(mp.size() < mp2.size())
		{
			swap(mp, mp2);
		}
		for(auto [it, fr] : mp2)
		{
			mp[it] += fr;
		}
	}
	if(d[src])
	{
		mp[d[src]] += v[src];
		while(true)
		{
			auto it = mp.upper_bound(d[src]);
			if(it == mp.end())	break;
			if(it->second <= v[src])	
			{
				v[src] -= it->second;
				mp.erase(it);
				continue;
			}
			it->second -= v[src];
			break;
		}
	} 
	swap(mp, mp2);
	return ;
}

int main()
{
	fastio;
	cin >> n >> m >> k;
	for(int i = 2; i <= n; i++)
	{
		lg p;
		cin >> p;
		adj[p].push_back(i);
	}
	for(int i = 1; i <= m; i++)
	{
		lg node, day, score;
		cin >> node >> day >> score;
		d[node] = day;
		v[node] = score;
	}
	solve(1);
	lg ans = 0;
	for(auto [a, b] : mp2)	ans += b;
	cout << ans << '\n';

    return 0;
}


/*
dp[src][max] = max(dp[par][v[i]]+w[i], dp[src][max-1])
*/
#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...