제출 #57976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57976		thiago4532	Chase (CEOI17_chase)	C++17	0 / 100	3810 ms	96996 KiB

chase

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10, maxv = 110;
int dp[2][maxn][maxv], p[maxn], n, v, pai[maxn], gain[maxn];
vector<int> grafo[maxn];

void dfs(int u){
	for(auto v : grafo[u]){
		if(pai[u] == v) continue;
		pai[v] = u;
		gain[u] += p[v];
		dfs(v);
	}
}

int solve1(int u, int j){
	if(j == 0) return 0;
	if(dp[0][u][j] != -1) return dp[0][u][j];

	int ans=-0x3f3f3f3f;
	for(auto v : grafo[u]){
		if(pai[u] == v) continue;
		int resp = max(solve1(v, j), solve1(v, j-1) + gain[v] - p[u]);

		ans = max(ans, resp);
	}
	return dp[0][u][j] = ans;
}

int solve2(int u, int j){
	if(j == 0) return 0;
	if(dp[1][u][j] != -1) return dp[1][u][j];

	int ans=-0x3f3f3f3f;
	for(auto v : grafo[u]){
		if(pai[u] == v) continue;
		int resp = max(solve2(v, j), solve2(v, j-1) + gain[u] - p[v]);

		ans = max(ans, resp);
	}
	return dp[1][u][j] = ans;
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	memset(dp, -1, sizeof dp);
	cin >> n >> v;
	for(int i=1;i<=n;i++)
		cin >> p[i];

	for(int i=1;i<n;i++){
		int a, b;
		cin >> a >> b;
		grafo[a].push_back(b);
		grafo[b].push_back(a);
	}
	dfs(1);
	solve1(1, v);
	solve2(1, v);

	int resp = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=v;j++){
			for(auto u : grafo[i]){
				resp = max(resp, dp[1][i][j] + dp[0][u][v-j]);
			}
		}
	}

	cout << resp << "\n";
	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30