Codeforces 735E - Ostap and Tree

#动态规划 #树形动态规划
Published on 2016-12-05

题目地址

描述

在一个含有 n(n≤100)n(n\le 100) 个节点的树中，你可以将每个节点涂成黑色或者白色，请问有多少种涂色方案，能够使得对于任意节点，都有一个黑色节点与其距离不超过 K(K≤min(20,n−1))K(K\le \min(20, n - 1))。对方案数模 109+7{10}^9 + 7。

分析

本题中，若一棵子树还有点未被黑色点覆盖，那么它是可以被子树外的黑点覆盖的，而且这个子树内的黑点，也可以覆盖被子树外的白点，我们必须把这些状态记录下来。

设 dp(i,j,k)dp(i, j, k) 为给 ii 为根的子树涂色方案数，满足离根最近的黑点距离根的距离为 jj（不存在则为 −1-1），以及离根最远的未被覆盖的白点距离根的距离为 kk（不存在则为 −1-1）。那么我们考虑转移，对于一个根，我们顺序 考虑它的所有儿子，则我们每次要做的就是将两棵子树合并（将一棵新的子树接在根所在的子树上）。合并的时候，考虑刷表法，分别枚举两棵子树中的 (j,k)(j, k)，得到两个二元组 (a,b)(a, b) 和 (c,d)(c, d)，则我们只需要将 (a,b)(a, b) 和 (c,d)(c, d) 按照其定义合并即可。注意如果离根最近的黑点距离根的距离超过了 KK，我们要将其置为 −1-1。

每一条边都需要合并一次，所以只会做 n−1n - 1 次合并，合并的时间为 k4k^4，所以时间复杂度为 O(nk4)O(nk^4)。

代码

//  Created by Sengxian on 2016/12/05.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Codeforces 735E DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX_N = 100 + 3, MAX_K = 20 + 3, MOD = 1000000007;

#define len(x) ((int)x.size())
vector<int> G[MAX_N];
int n, K, dp[MAX_N][MAX_K][MAX_K];

void Dp(int u, int fa = -1) {
    memset(dp[u], 0, sizeof dp[u]);
    dp[u][-1 + 1][0 + 1] = 1, dp[u][0 + 1][-1 + 1] = 1;

    for (int i = 0; i < len(G[u]); ++i) {
        int v = G[u][i];
        if (v == fa) continue;
        Dp(v, u);

        static int t[MAX_K][MAX_K];
        memset(t, 0, sizeof t);
        for (int a = -1; a <= K; ++a)
            for (int b = -1; b <= K; ++b) if (dp[u][a + 1][b + 1])
                for (int c = -1; c <= K; ++c)
                    for (int d = -1; d <= K; ++d) if (dp[v][c + 1][d + 1]) {
                        bool f1 = b == -1, f2 = d == -1;
                        if (!f1 && c != -1 && b + c + 1 <= K) f1 = true;
                        if (!f2 && a != -1 && d + a + 1 <= K) f2 = true;

                        int e = -1;
                        if (a == -1 && c == -1) e = -1;
                        else if (a == -1) e = c + 1;
                        else if (c == -1) e = a;
                        else e = min(a, c + 1);
                        if (e > K) e = -1;

                        if (f1 && f2) (t[e + 1][-1 + 1] += (ll)dp[u][a + 1][b + 1] * dp[v][c + 1][d + 1] % MOD) %= MOD;
                        else if (f1) (t[e + 1][d + 1 + 1] += (ll)dp[u][a + 1][b + 1] * dp[v][c + 1][d + 1] % MOD) %= MOD;
                        else if (f2) (t[e + 1][b + 1] += (ll)dp[u][a + 1][b + 1] * dp[v][c + 1][d + 1] % MOD) %= MOD;
                        else (t[e + 1][max(b, d + 1) + 1] += (ll)dp[u][a + 1][b + 1] * dp[v][c + 1][d + 1] % MOD) %= MOD;
                    }

        memcpy(dp[u], t, sizeof t);
    }
}

int main() {
    scanf("%d%d", &n, &K);
    for (int i = 0, u, v; i < n - 1; ++i) {
        scanf("%d%d", &u, &v), --u, --v;
        G[u].push_back(v), G[v].push_back(u);
    }

    Dp(0);
    int ans = 0;
    for (int i = 0; i <= K; ++i) (ans += dp[0][i + 1][-1 + 1]) %= MOD;
    printf("%d\n", ans);
    return 0;
}
Codeforces 741D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths