제출 #58011

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

chase

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10, maxv = 110;
int dp[maxn][maxv][2], 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 solve(int u, int j, bool usa){
	if(j < 0 || (j == 0 && !usa)) return 0;
	if(dp[u][j][usa] != -1) return dp[u][j][usa];

	int ans = (usa ? gain[u] : 0);
	for(auto v : grafo[u]){
		if(pai[u] == v) continue;
		ans = max(ans, max(solve(v, j, 0), solve(v, j-1, 1)) + (usa ? gain[u] : 0));
	}
	return dp[u][j][usa] = ans;
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	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);
	}

	int resp=0;
	for(int u=1;u<=n;u++){
		if(u > 1 && n > 1010) break;
		memset(dp, -1, sizeof dp);
		memset(pai, 0, sizeof pai);
		memset(gain, 0, sizeof gain);
		dfs(u);

		for(int j=1;j<=v;j++) resp = max(resp, max(solve(u, v, 0), solve(u, v-1, 1)));
	}
	cout << resp << "\n";
	return 0;
}

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