给定一个n个点的树,把其中一些点涂成黑色,使得对于每个点,其最近的黑点的距离不超过K.
树形DP.
设置状态f[i][j]:
当j <= K时:
合法状态,表示i的子树中到根的最近黑点距离为j的方案数.
当 K < j <= 2K时:
不合法状态,表示i的子树中,需要在上面补充黑点,且这个黑点到i的距离应该至多为(2K - j + 1).
对于这个状态的另外一种理解方式是:i的子树中,距离i最近的黑点距离超过K,距离i最远的黑点距离为j,方案数.
设计这样状态的动机在于:
如果仅仅有j <= K的状态,那么可能仅仅满足了某些点的要求,而没有满足所有点, 或者, 仅仅考虑子树中对于点的影响, 而不考虑祖先, 换言之, 状态具有后效性.
这样的状态设置是精妙的, 实际编程中大大减少了编程复杂度.
转移的时候, 依次加入点x的每一个儿子树, 然后枚举已经形成的树找到过的j, 和对于这个子树的k:
如果j + (k + 1) <= 2K + 1, 那么说明把这个方案加到树里可以直接构成一个合法方案, 那么直接统计.
否则,说明需要上面的黑点,那么放进不合法状态中.
实现的时候开一个临时数组即可.
具体方程和细节见代码.
初始化的时候:
f[x][0] = f[x][k+1] = 1;
刚开始的时候只有x一个节点, 然后这个节点选与不选两种方案.
答案统计f[1][i](i <= K)即可.
#include <cstdio>
#include <algorithm>
#define ll long long
#define For(i,j,k) for(ll i=j;i<=k;i++)
using namespace std;
ll mo=1e9+7;
ll poi[10001],F[10001],nxt[10001], dep[1001],f[1001][1001],tmp[1001],ans,n,k,x,y,cnt;
bool vis[1001];
inline void add(ll x,ll y){poi[++cnt]=y;nxt[cnt]=F[x];F[x]=cnt;}
inline void dfs(ll x) {
vis[x] = 1;
f[x][0] = 1;
f[x][k+1] = 1;
for(ll i=F[x];i;i=nxt[i]) {
ll ne = poi[i];
if(vis[ne]) continue;
dep[ne] = dep[x] + 1;
dfs(ne);
For(j,0,2*k) tmp[j]=0;
For(j,0,2*k) For(t,0,2*k+1) {
if(j+t<=2*k)
tmp[min(j,t + 1)] += f[x][j] * f[ne][t], tmp[min(j,t+1)] %= mo;
else
tmp[max(j,t + 1)] += f[x][j] * f[ne][t], tmp[max(j,t+1)] %= mo;
}
For(j, 0,2*k) f[x][j]=tmp[j];
}
}
int main() {
#ifdef orz
freopen("input", "r", stdin);
#endif
scanf("%lld %lld", &n, &k);
if(k == 0) return puts("1") & 0;
For(i,1,n-1) {
scanf("%lld %lld", &x, &y);
add(x, y);
add(y, x);
}
dfs(1);
For(i,0,k) ans+=f[1][i],ans%=mo;
printf("%lld", ans);
}
代码魔改自:
一个神犇的博客