QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#75561 | #4815. Flower's Land | LG_Monkey | WA | 2ms | 11660kb | C++14 | 3.2kb | 2023-02-05 20:29:50 | 2023-02-05 20:29:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define pb push_back
#define se second
#define int long long
int n, k, a[40010], ans[40010];
vector<int> g[40010];
bool vis[40010];
int nod, siz[40010], mx[40010], hvy;
int dfn[40010], tim, cnt[40010], mxd, val[40010], dp[40010][3010], dp2[40010][310], G[40010][310], FA[40010];
void getnod(int u, int fa) {
nod++;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == fa || vis[v]) continue;
getnod(v, u);
}
}
void chkhvy(int u, int fa) {
siz[u] = 1;
mx[u] = -1;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == fa || vis[v]) continue;
chkhvy(v, u);
siz[u] += siz[v];
mx[u] = max(mx[u], siz[v]);
}
mx[u] = max(mx[u], nod - siz[u]);
if (mx[u] < mx[hvy]) hvy = u;
}
int gethvy(int u) {
nod = 0;
getnod(u, 0);
hvy = 0;
mx[hvy] = 1e12;
chkhvy(u, 0);
return hvy;
}
void getdfn(int u, int fa) {
cnt[u] = 1;
dfn[u] = ++tim;
val[dfn[u]] = u;
mxd = max(mxd, dfn[u]);
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (vis[v] || v == fa) continue;
FA[v] = u;
getdfn(v, u);
cnt[u] += cnt[v];
}
}
void dfs(int u) {
nod = 0;
getnod(u, 0);
if (nod < k) return;
cout << " dfs into " << u << "\n";
mxd = 0;
vis[u] = 1;
FA[u] = 0;
tim = 0; getdfn(u, 0);
for (int i = 0; i <= mxd; i++)
for (int j = 0; j <= k + 1; j++) dp[i][j] = dp2[i][j] = -1e12, G[i][j] = -1e12;
dp[1][1] = a[u];
for (int i = 1; i <= mxd; i++)
for (int j = 1; j <= k + 1; j++) {
dp[i][j] = max(dp[dfn[FA[val[i]]]][j - 1] + a[val[i]], dp[i][j]);
dp[i][j] = max(dp[i][j], G[i][j - 1] + a[val[i]]);
// dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + a[val[i + 1]]);
G[i + cnt[val[i]]][j] = max(G[i + cnt[val[i]]][j], max(G[i][j], dp[i][j]));
}
for (int i = 0; i <= mxd; i++)
for (int j = 0; j <= k + 1; j++) G[i][j] = -1e12;
dp2[mxd][1] = a[val[mxd]];
for (int i = mxd; i >= 1; i--) {
dp2[i][1] = max(dp2[i][1], a[val[i]]);
for (int j = 1; j <= k + 1; j++) {
dp2[i][j] = max(dp2[i][j], G[i][j - 1] + a[val[i]]);
// dp2[i - 1][j + 1] = max(dp2[i - 1][j + 1], dp2[i][j] + a[val[i - 1]]);
// cout << FA[val[i]] << " QAQ\n";
dp2[dfn[FA[val[i]]]][j + 1] = max(dp2[dfn[FA[val[i]]]][j + 1], dp2[i][j] + a[FA[val[i]]]);
// dp2[i + cnt[val2[i]]][j + 1] = max(dp2[i + cnt[val2[i]]][j + 1], dp[i][j] + a[val2[i + cnt[val2[i]]]]);
G[i - 1][j] = max(G[i - 1][j], max(G[i][j], dp2[i][j]));
}
}
for (int i = 1; i <= mxd; i++) {
int res = 0;
res = max(res, dp[i][k]);
res = max(res, dp2[i][k]);
for (int l = 1; l <= k; l++) {
int r = k + 1 - l;
int L = l, R = r;
// res = max(res, dp[i][L] + dp2[i][R] - a[val[i]]);
}
ans[val[i]] = max(ans[val[i]], res);
}
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (vis[v]) continue;
dfs(gethvy(v));
}
}
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
}
dfs(gethvy(1));
for (int i = 1; i <= n; i++) cout << ans[i] << " ";
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 11660kb
input:
5 3 6 10 4 3 4 3 4 4 2 2 5 5 1
output:
dfs into 2 20 20 17 13 17
result:
wrong output format Expected integer, but "dfs" found