| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 571735 | piOOE | Chase (CEOI17_chase) | C++17 | 0 ms | 0 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.
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
const int N = 100001;
vector<int> g[N];
int n, k, parent[N], depth[N];
ll p[N], pp[N];
void dfs(int v) {
for (int to: g[v]) {
if (to != parent[v]) {
parent[to] = v;
depth[to] = depth[v] + 1;
dfs(to);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> p[i];
}
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
--a, --b;
g[a].push_back(b);
g[b].push_back(a);
}
int ans = 0;
for (int r = 0; r < n; ++r) {
parent[r] = r;
depth[r] = 1;
dfs(r);
for (int v = 0; v < n; ++v) {
if (depth[v] <= k) {
memcpy(pp, p, sizeof(pp[0]) * n);
ll cntnow = 0, cntnext = 0;
int x = v;
while (x != r) {
cntnow += pp[x];
for (int to: g[x]) {
pp[x] += pp[to];
pp[to] = 0;
}
x = parent[x];
}
{
cntnow += pp[x];
for (int to: g[x]) {
pp[x] += pp[to];
pp[to] = 0;
}
}
{
x = v;
while (x != r) {
cntnext += pp[x];
x = parent[x];
}
cntnext += pp[r];
}
ans = max(ans, cntnext - cntnow);
}
}
}
cout << ans;
return 0;
}