题意

给出一棵 n(n\leq 100) 个点的树，要求给每个点染成黑色或白色，使得每个点都存在至少一个黑点与它的距离不大于 k(0\leq k\leq\min(20,n-1))。求染色方案数模 10^9+7。

题解

这个题的方法很妙啊。。官方题解给的做法是 O(nk^4) 的，实际上有一种 O(nk^2) 的做法。

考虑 DP。设 f(u,i) 表示 u 子树中，距 u 最近的黑点与 u 的距离为 i 的方案数（i\leq k），或与 u 距离不小于 i 的点都满足的方案数（i>k）。逐个加入儿子 v，枚举 f(u,i) 和 f(v,j)。若 i+j\leq k，那么说明最长的这条 i+j+1 的链上的点都可以到达一侧的黑点；否则不行。具体地，转移可以写成

代码

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN=220;
const int P=1E9+7;
int n, k;
vector<int> g[MAXN];
int f[MAXN][MAXN], t[MAXN];
void dfs(int u, int p)
{
    f[u][0]=f[u][k+1]=1;
    for (int v:g[u])
        if (v!=p)
        {
            dfs(v, u);
            memcpy(t, f[u], sizeof t);
            memset(f[u], 0, sizeof f[u]);
            for (int i=0; i<=2*k; i++)
                for (int j=0; j<=2*k; j++)
                {
                    int& st=i+j<=2*k?f[u][min(i, j+1)]:f[u][max(i, j+1)];
                    st=(st+1ll*t[i]*f[v][j])%P;
                }
        }
}
int main()
{
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for (int i=1; i<n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    int ans=0;
    for (int i=0; i<=k; i++) ans=(ans+f[1][i])%P;
    printf("%d\n", ans);
    return 0;
}