[USACO17DEC] Barn Painting G

GitHub跳转原题关系图返回列表

设 dp[u][c] 表示 u 染成颜色 c 时整棵子树的合法方案数，再把每个儿子所有不同色状态的方案数乘起来。

OJ: luogu

题目 ID: P4084

难度:普及+/提高

标签:树形DP动态规划计数dp树

日期: 2026-06-21 03:36

目录

  1. 题意
  2. 思路
    1. DP 转移方程
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给一棵树，要用 3 种颜色给所有点染色。

要求：

  • 每条边两端颜色不同
  • 部分点已经预先指定颜色

求合法染色方案数，对 1e9+7 取模。

思路

先看一个可以直接验证想法的朴素解：

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
const long long MOD = 1000000007LL;

int n, k;
int fixed_color[MAXN];
int color_arr[MAXN];
int adj[MAXN][MAXN];
long long ans;

void dfs(int u) {
    if (u > n) {
        ans = (ans + 1) % MOD;
        return;
    }

    for (int c = 1; c <= 3; c++) {
        if (fixed_color[u] != 0 && fixed_color[u] != c) {
            continue;
        }

        bool ok = true;
        for (int v = 1; v < u; v++) {
            if (adj[u][v] && color_arr[v] == c) {
                ok = false;
                break;
            }
        }
        if (!ok) {
            continue;
        }

        color_arr[u] = c;
        dfs(u + 1);
        color_arr[u] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 这是一个小数据精确暴力：
    // 直接枚举每个点的颜色，再检查是否满足相邻点不同色。
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        fixed_color[i] = 0;
        color_arr[i] = 0;
        for (int j = 1; j <= n; j++) {
            adj[i][j] = 0;
        }
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = adj[v][u] = 1;
    }

    for (int i = 1; i <= k; i++) {
        int u, c;
        cin >> u >> c;
        fixed_color[u] = c;
    }

    ans = 0;
    dfs(1);
    cout << ans % MOD << '\n';
    return 0;
}

brute.cpp 直接枚举每个点的颜色，再检查是否满足相邻点不同色和预染色限制。 这个方法完全正确，但复杂度是 3^n，只能做小数据。

这题是很标准的树形 DP 计数。

设 dp[u][c] 表示：

  • u 染成颜色 c
  • 且整棵 u 子树合法染色
  • 的方案数

DP 转移方程

若 u 没有被固定成其它颜色，则：

dp[u][c]=∏v∈son(u)∑cc≠cdp[v][cc] dp[u][c]=\prod_{v \in son(u)} \sum_{cc \ne c} dp[v][cc]

若 u 已经被固定颜色 fixed[u]，则所有 c != fixed[u] 的状态为 0。 最终答案为：

dp[1][1]+dp[1][2]+dp[1][3] dp[1][1]+dp[1][2]+dp[1][3]

如果 u 已经被固定成别的颜色，那么这个状态直接为 0。

否则，对每个儿子 v：

  • v 的颜色只能从另外两种里选

所以这个儿子的贡献就是：

dp[v][1] + dp[v][2] + dp[v][3] 中去掉和 c 相同的那一项

再把所有儿子的贡献乘起来，就是 dp[u][c]。

由于不同儿子子树之间互不影响，这个乘法是成立的。

最后答案就是：

dp[1][1] + dp[1][2] + dp[1][3]

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
const long long MOD = 1000000007LL;

int n, k;
vector<int> g[MAXN];
int fixed_color[MAXN];
int parent_arr[MAXN];
long long dp[MAXN][4];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        fixed_color[i] = 0;
        for (int c = 1; c <= 3; c++) {
            dp[i][c] = 0;
        }
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= k; i++) {
        int u, c;
        cin >> u >> c;
        fixed_color[u] = c;
    }

    vector<int> order;
    order.reserve(n);
    stack<int> st;
    st.push(1);
    parent_arr[1] = 0;

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        order.push_back(u);
        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == parent_arr[u]) {
                continue;
            }
            parent_arr[v] = u;
            st.push(v);
        }
    }

    for (int idx = (int)order.size() - 1; idx >= 0; idx--) {
        int u = order[idx];

        for (int c = 1; c <= 3; c++) {
            if (fixed_color[u] != 0 && fixed_color[u] != c) {
                dp[u][c] = 0;
                continue;
            }

            long long ways = 1;
            for (size_t i = 0; i < g[u].size(); i++) {
                int v = g[u][i];
                if (v == parent_arr[u]) {
                    continue;
                }

                long long child_ways = 0;
                for (int cc = 1; cc <= 3; cc++) {
                    if (cc == c) {
                        continue;
                    }
                    child_ways = (child_ways + dp[v][cc]) % MOD;
                }
                ways = ways * child_ways % MOD;
            }
            dp[u][c] = ways;
        }
    }

    long long ans = (dp[1][1] + dp[1][2] + dp[1][3]) % MOD;
    cout << ans << '\n';
    return 0;
}

复杂度

每个点只会被处理一次，每次只枚举 3 种颜色和它的所有儿子。

所以时间复杂度是 O(n)O(n)，空间复杂度是 O(n)O(n)。

总结

这题的核心状态非常经典：

  • dp[u][颜色]

而转移本质就是：

  • 当前点定色后
  • 儿子只能从剩下两种颜色里选

是树上有限颜色计数 DP 的标准模板。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析