| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 571735 | piOOE | Chase (CEOI17_chase) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}