Submission #98135

#TimeUsernameProblemLanguageResultExecution timeMemory
98135luciocfChase (CEOI17_chase)C++14
0 / 100
5 ms2176 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 1e3+10; const int maxv = 110; typedef long long ll; int n, c; int num[maxn]; ll soma[maxn], dp[maxn][maxv][2]; vector<int> grafo[maxn]; void dfs(int u, int p) { for (auto v: grafo[u]) { if (v == p) continue; ll x = (ll)soma[v]-(ll)num[u]; for (int i = 0; i <= c; i++) { dp[v][i][0] = max(dp[u][i][0], dp[u][i][1]); if (!i) continue; dp[v][i][1] = dp[u][i-1][0]; dp[v][i][1] = x+max(dp[v][i][1], dp[u][i-1][1]); } } } int main(void) { cin >> n >> c; for (int i = 1; i <= n; i++) cin >> num[i]; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; grafo[u].push_back(v); grafo[v].push_back(u); } for (int u = 1; u <= n; u++) for (auto v: grafo[u]) soma[u] += (ll)num[v]; ll ans = 0LL; for (int i = 1; i <= n; i++) { memset(dp, 0, sizeof dp); dp[i][1][1] = soma[i]; dfs(i, 0); for (int j = 1; j <= n; j++) for (int l = 0; l <= c; l++) ans = max({ans, dp[j][l][0], dp[j][l][1]}); } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...