# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
104952 | eriksuenderhauf | Chase (CEOI17_chase) | C++11 | 500 ms | 253048 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 1; i <= (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
vi adj[MAXN];
ll p[MAXN], dp[2][MAXN][101], ans = 0, sum[MAXN];
int vv;
void dfs(int u, int pa)
{
ll sm = sum[u] - p[pa];;
ll m1[101] = {0}, m2[101] = {0};
dp[0][u][0] = dp[1][u][0] = 0;
dp[1][u][1] = sm + p[pa];
for (int v: adj[u]) if (v != pa)
{
dfs(v, u);
for (int i = 1; i <= vv; i++)
{
dp[0][u][i] = max(dp[0][u][i], max(dp[0][v][i], dp[0][v][i - 1] + sm));
dp[1][u][i] = max(dp[1][u][i], max(dp[1][v][i], dp[1][v][i - 1] + sm + p[pa] - p[v]));
if (dp[0][v][i] >= m1[i])
m2[i] = m1[i], m1[i] = dp[0][v][i];
else if (dp[0][v][i] > m2[i])
m2[i] = dp[0][v][i];
}
}
for (int v: adj[u])
{
if (v == pa) continue;
if (vv > 0) ans = max(ans, sm + p[pa] + dp[0][v][vv - 1]);
for (int i = 0; i <= vv; i++)
{
ll x = max(dp[1][v][i], i == 0 ? 0 : dp[1][v][i - 1] + sm + p[pa] - p[v]);
if (m1[vv - i] == dp[0][v][vv - i])
ans = max(ans, x + m2[vv - i]);
else
ans = max(ans, x + m1[vv - i]);
}
}
}
int main()
{
int n;
ni(n), ni(vv);
nal(p, n);
for (int i = 1; i < n; i++)
{
int u, v;
ni(u), ni(v);
adj[u].pb(v);
adj[v].pb(u);
sum[u] += p[v], sum[v] += p[u];
}
dfs(1, 0);
prl(ans);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |