Codeforces 735E 树形DP

灰太狼 2023-08-17 17:22 116阅读 0赞

题意：给你一棵树，你需要在这棵树上选择一些点染成黑色，要求染色之后树中任意节点到离它最近的黑色节点的距离不超过m，问满足这种条件的染色方案有多少种？

思路：设dp\[x\]\[i\]为以x为根的子树中，离x点最近的点的距离是i，并且满足题目中的限制条件的方案数。我们假设已经计算了x的一些子树对x的贡献，我们考虑x的一个还没产生贡献的子树y对x的贡献。用数组f作为临时变量。我们枚举x的距离i和y的距离j,容易发现有两种情况：i + j + 1 <= 2 \* m + 1，这种时候不会出现不符合题目条件的点，直接转移即可：f\[min(i, j + 1)\] += dp\[x\]\[i\] \* dp\[y\]\[j\]。第二种情况：i + j + 1 > 2 \*m + 1, 那么就不能直接转移了，因为如果转移了会出现不符合题目中的条件的点。但是我们可以保存这两者中的最大值，作为最远点来看他们仍然是合法的，而且它们仍有可能和后面的子树形成新的答案。有一个细节需要注意一下：在处理第一棵子树的时候，我们把dp\[x\]\[0\]和dp\[x\]\[m + 1\]设置为0，第一个的原因是因为子树和根节点本身可以形成合法情况。第二种操作相当于取了个巧，本质是把dp\[v\]\[i\]赋值给dp\[x\]\[i + 1\]。

代码：

#include <bits/stdc++.h>
    #define LL long long
    #define INF 0x3f3f3f3f
    #define db double
    #define pii pair<int, int>
    using namespace std;
    const LL mod = 1e9 + 7;
    const int maxn = 210;
    LL dp[maxn][maxn], f[maxn];
    vector<int> G[maxn];
    int n, m;
    void add(int x, int y) {
    	G[x].push_back(y);
    	G[y].push_back(x);
    }
    void dfs(int x, int fa) {
    	dp[x][0] = dp[x][m + 1] = 1;
    	for (auto y : G[x]) {
    		if(y == fa) continue;
    		dfs(y, x);
    		memset(f, 0, sizeof(f));
    		for (int i = 0; i <= 2 * m + 1; i++) {
    			for (int j = 0; j <= 2 * m; j++) {
    				if(i + j <= 2 * m) {
    					int p = min(i, j + 1);
    					f[p] = (f[p] + (dp[x][i] * dp[y][j]) % mod) % mod;
    				} 
    				else {
    					int p = max(i, j + 1);
    					f[p] = (f[p] + (dp[x][i] * dp[y][j]) % mod) % mod;
    				}
    			}
    		}
    		for (int i = 0; i <= 2 * m; i++) {
    			dp[x][i] = f[i];
    		}
    	}
    }
    int main() {
    	int x, y;
    	scanf("%d%d", &n, &m);
    	for (int i = 1; i < n; i++) {
    		scanf("%d%d", &x, &y);
    		add(x, y);
    	}
    	dfs(1, -1);
    	LL ans = 0;
    	for (int i = 0; i <= m; i++) {
    		ans = (ans + dp[1][i]) % mod;
    	}
    	printf("%lld\n", ans);
    }

转载于:https://www.cnblogs.com/pkgunboat/p/11436693.html