| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1247508 | MateiKing80 | Chase (CEOI17_chase) | C++20 | 0 ms | 0 KiB |
#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][nod] + sum, dp[0][i - 1][nod] + 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];
memset(dp1, -inf, sizeof(dp1));
memset(dp2, -inf, sizeof(dp2));
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);
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
*/