QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#75561#4815. Flower's LandLG_MonkeyWA 2ms11660kbC++143.2kb2023-02-05 20:29:502023-02-05 20:29:52

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 20:29:52]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11660kb
  • [2023-02-05 20:29:50]
  • 提交

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