社区讨论

时间复杂度n的4次方能16分吗?

P14637[NOIP2025] 树的价值参与者 6已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@milsnyh0
此快照首次捕获于
2025/11/30 22:07
3 个月前
此快照最后确认于
2025/12/03 17:05
3 个月前
查看原帖
rt
加了点剪枝,但是没有认真卡常。
CPP
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define GL return
#define HF 0

const int N = 20, M = (1 << 13) + 20;

int test, n, m, fa[N], f[N][M], tmp[M];
vector<int> edges[N];

int mex (int x) {
	for (int i = 0; i < n; i++) {
		if (x >> i & 1) {
			
		} else {
			return i;
		}
	}
	return n;
}

inline void dfs (const int &x) {
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			f[x][1 << i] = 1;
		} else {
			f[x][1 << i] = 0;
		}
	}
	for (auto y : edges[x]) {
		dfs(y);
		for (int i = 0; i < 1 << n; i++) {
			tmp[i] = -64000;
		}
		for (int i = 0; i < 1 << n; i++) {
			if (f[x][i] >= 0) {
				for (int j = 0; j < 1 << n; j++) {
					if (f[y][j] >= 0) {
						tmp[i | j] = max(tmp[i | j], f[x][i] + f[y][j] - mex(i) + mex(i | j));
					}
				}
			}
		}
		for (int i = 0; i < 1 << n; i++) {
			f[x][i] = tmp[i];
		}
	}
}

inline void solve () {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		edges[i].clear();
		for (int j = 0; j < 1 << n; j++) {
			f[i][j] = -64000;
		}
	}
	for (int i = 2; i <= n; i++) {
		scanf("%d", &fa[i]);
		edges[fa[i]].push_back(i);
	}
	dfs(1);
	ll ans = -64000;
	for (int i = 0; i < 1 << n; i++) {
		ans = max(ans, 1ll * f[1][i]);
	}
	printf("%lld\n", ans);
	GL;
}

int main() {
	for (scanf("%d", &test); test--; solve());
	GL HF;
}

回复

10 条回复,欢迎继续交流。

正在加载回复...