【Barn Painting--G】题解

题干信息解读

Farmer John 有一个包含 N 个谷仓的农场，部分谷仓已被涂色，部分未被涂色。他希望用三种颜色（红、蓝、绿）给剩余谷仓涂色，同时满足以下条件：

1.所有直接相连的谷仓颜色不能相同。
2.已涂色的谷仓颜色不能更改。

已知谷仓之间的连接关系构成一棵树（无环），求满足条件的涂色方案数，结果对 $10^9+7$ 取模。

整体做题思路

1.树的结构特性：由于谷仓连接关系是一棵树，可以任选一个根节点，将树转换为有根树，便于进行树形 DP。
2.动态规划状态定义：定义dp[u][c]表示节点u涂颜色c时，以u为根的子树的合法涂色方案数。
3.状态转移：
①对于已涂色的节点u，其颜色c固定，遍历所有子节点v，计算每个子节点除c外的颜色方案数之和。
②对于未涂色的节点u，尝试三种颜色，遍历所有子节点v，计算每个子节点除当前颜色外的颜色方案数之和。
4.结果计算：根节点的三种颜色方案数之和即为答案。

难点和注意事项

1.树的遍历方向：需先处理子树，再处理父节点，因此使用后序遍历（DFS）。
2.模运算处理：由于方案数可能很大，每次计算后需对 $10^9+7$ 取模，避免溢出。
3.已涂色节点限制：已涂色节点的颜色不可更改，需在状态转移时排除冲突颜色。

AC代码（如有雷同，纯属巧合）

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

vector<int> adj[MAXN];      // 邻接表存储树结构
int fixed_color[MAXN];      // 已涂色节点的颜色，0表示未涂色
long long dp[MAXN][4];      // dp[u][c]表示节点u涂颜色c的方案数

// 深度优先搜索处理树
void dfs(int u, int parent) {
    // 如果节点u已涂色，初始化其dp值
    if (fixed_color[u] != 0) {
        int c = fixed_color[u];
        dp[u][c] = 1;
    } else {
        // 未涂色节点可以选择三种颜色
        for (int c = 1; c <= 3; c++) {
            dp[u][c] = 1;
        }
    }
    
    // 遍历所有子节点
    for (int v : adj[u]) {
        if (v == parent) continue;  // 避免处理父节点
        dfs(v, u);  // 递归处理子树
        
        // 更新当前节点的dp值
        if (fixed_color[u] != 0) {
            int c = fixed_color[u];
            long long sum = 0;
            for (int cc = 1; cc <= 3; cc++) {
                if (cc == c) continue;  // 相邻节点颜色不能相同
                sum = (sum + dp[v][cc]) % MOD;
            }
            dp[u][c] = (dp[u][c] * sum) % MOD;
        } else {
            // 未涂色节点，尝试三种颜色
            for (int c = 1; c <= 3; c++) {
                long long sum = 0;
                for (int cc = 1; cc <= 3; cc++) {
                    if (cc == c) continue;  // 相邻节点颜色不能相同
                    sum = (sum + dp[v][cc]) % MOD;
                }
                dp[u][c] = (dp[u][c] * sum) % MOD;
            }
        }
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    
    // 初始化已涂色节点数组
    memset(fixed_color, 0, sizeof(fixed_color));
    
    // 读取边信息
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    
    // 读取已涂色节点信息
    for (int i = 0; i < k; i++) {
        int b, c;
        cin >> b >> c;
        fixed_color[b] = c;
    }
    
    // 任选根节点，这里选择1
    int root = 1;
    memset(dp, 0, sizeof(dp));
    dfs(root, -1);
    
    // 计算最终结果
    long long ans = 0;
    for (int c = 1; c <= 3; c++) {
        ans = (ans + dp[root][c]) % MOD;
    }
    
    cout << ans << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O (N)。每个节点和每条边仅被处理一次，状态转移的颜色枚举为常数时间。
• 空间复杂度：O (N)。主要用于存储树结构和 DP 数组。

该算法通过树形 DP 高效地计算了满足条件的涂色方案数，确保在大规模数据下仍能快速求解。