Submission #1247514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247514		MateiKing80	Chase (CEOI17_chase)	C++20	30 / 100	447 ms	167768 KiB

chase

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int N = 1e5 + 5, V = 105, inf = 1e16;

int dp[2][V][N], p[N], v, ans;
vector<int> vec[N];

void dfs(int nod, int papa) {
	int sum = 0;
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		sum += p[i];
	}
	for (int i = 0; i <= v; i ++) {
		dp[0][i][nod] = max(dp[0][i][papa], dp[1][i][papa]);
		if (i)
			dp[1][i][nod] = max(dp[1][i - 1][papa] + sum, dp[0][i - 1][papa] + sum);
	}
	for (auto i : vec[nod])
		if (i != papa)
			dfs(i, nod);
}

signed main() {
	int n;
	cin >> n >> v;
	for (int i = 1; i <= n; i ++)
		cin >> p[i];
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j <= v; j ++)
			dp[0][j][i] = dp[1][j][i] = -inf;
	for (int i = 1; i < n; i ++) {
		int x, y;
		cin >> x >> y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	dp[0][0][1] = 0;
	dp[1][1][1] = 0;
	for (auto i : vec[1])
		dp[1][1][1] += p[i];
	for (auto i : vec[1])
		dfs(i, 1);
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j <= v; j ++)
			ans = max(ans, max(dp[0][j][i], dp[1][j][i]));
	cout << ans << '\n';
}

/*
cred ca problema este ca poti sari cateva locuri in care nu pui paine
si se schimba dinamica
avem o alta dinamica de tipul: dp1[0/1], dp2[0/1] ca inainte dar [0/1] inseamna ca
*/

/*
subtaskforces
deci
bag ala de pleaca de la 1
dp[nod][val][0/1] best thing pana la nod + am luat sau nu nod
*/

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