【Codeforces 735E】Ostap and Tree | Mrsrz's blog

树形 DP。

题目大意：

给定一棵树，要给一些结点染色，并且需要满足距离每个点最近的染色点离它的距离不超过 $k$。求方案数。

题解：

动态规划。

令 $f_{i,j}$ 表示以 $i$ 为根的子树中，有一个最近的黑点距离根为 $j$ 且距离 $j$ 以上的点都已经有对应的染色点。

也就是说，如果 $i$ 子树中全都有距离为 $k$ 以内的染色点，则 $j$ 表示其子树中最浅的一个染色点。反正 $j$ 就表示子树中最深的且到根路径上没有别的染色点的染色点。

转移的时候枚举 $j,t$，考察 $j+t+1$ 和 $2k+1$ 的大小关系进行转移即可。具体见代码的 dfs 部分。

时间复杂度 $O(nk^2)$。

Code：

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=114,md=1e9+7;
int n,k,dp[N][42],g[42];
vector<int>G[N];
inline void add(int&a,LL b){a=(a+b)%md;}
int dfs(int now,int pre){
    bool flg=0;
    int dep=1;
    int*f=dp[now];
    for(int to:G[now])if(to!=pre){
        dep=max(dfs(to,now)+1,dep);
        if(!flg){
            flg=1;
            for(int i=0;i<=2*k;++i)f[i+1]=dp[to][i];
        }else{
            memset(g,0,sizeof g);
            for(int i=0;i<=2*k+1;++i)
                for(int j=0;j<=2*k+1;++j)
                    if(i+j+1<=2*k+1)
                        add(g[min(i,j+1)],f[i]*(LL)dp[to][j]);
                    else
                        add(g[max(i,j+1)],f[i]*(LL)dp[to][j]);
            memcpy(f,g,sizeof g);
        }
    }
    if(dep==1)
        f[0]=f[k+1]=1;
    else{
        for(int i=1;i<=2*k+1;++i)add(f[0],f[i]);
    }
    return dep;
}
int main(){
    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)add(ans,dp[1][i]);
    printf("%d\n",ans);
    return 0;
}