P9414 「NnOI R1-T3」元组

P9414 「NnOI R1-T3」元组

树上背包

首先思考题意，每个方案都存在一个唯一的 \(x\)，所以我们可以枚举 \(x\)，计算有多少方案使得 \(\rm LCA\) 为 \(x\)。

\(x\) 上方的点一定不能选，那么就变成了在 \(x\) 子树内的选点问题。思考后可以发现，要满足题意，就是要满足 每个 \(son_u\) 子树中选的点 \(<k\)！那么这就是一个裸的树上背包问题，设 \(f_{u,i}\) 表示在 \(u\) 中选 \(i\) 个点的方案数，调整一下枚举上界即可。

复杂度 \(O(n^2)\)。

我竟然能做出来，难度虚高

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e3 + 10, mod = 1e9 + 7;
i64 n, p, k;
i64 f[N][N], sz[N], ans, tmp[N];
std::vector<int> e[N];
void dfs(int u, int fa) {
	sz[u] = 1;
	f[u][0] = f[u][1] = 1;
	for(auto v : e[u]) {
		if(v == fa) continue;
		dfs(v, u);
		for(int i = 0; i <= sz[u] + sz[v]; i++) tmp[i] = 0;
		for(int i = 0; i <= sz[u]; i++) {
			for(int j = 0; j <= std::min(k - 1, sz[v]); j++) {
				tmp[i + j] = (tmp[i + j] + f[u][i] * f[v][j]) % mod;
			}
		}
		for(int i = 1; i <= sz[u] + sz[v]; i++) f[u][i] = tmp[i];
		sz[u] += sz[v];
	}
	ans = (ans + f[u][p]) % mod;
}
void Solve() {
	std::cin >> n >> p >> k;
	for(int i = 1; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		e[u].pb(v), e[v].pb(u);
	}
	dfs(1, 0);
	std::cout << ans << "\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	Solve();

	return 0;
}