题干信息解读
Farmer John 有一个包含 N 个谷仓的农场，部分谷仓已被涂色，部分未被涂色。他希望用三种颜色（红、蓝、绿）给剩余谷仓涂色，同时满足以下条件：
1.所有直接相连的谷仓颜色不能相同。
2.已涂色的谷仓颜色不能更改。
已知谷仓之间的连接关系构成一棵树（无环），求满足条件的涂色方案数，结果对 109+710^9+7109+7 取模。
整体做题思路
1.树的结构特性：由于谷仓连接关系是一棵树，可以任选一个根节点，将树转换为有根树，便于进行树形 DP。
2.动态规划状态定义：定义dp[u][c]表示节点u涂颜色c时，以u为根的子树的合法涂色方案数。
3.状态转移：
①对于已涂色的节点u，其颜色c固定，遍历所有子节点v，计算每个子节点除c外的颜色方案数之和。
②对于未涂色的节点u，尝试三种颜色，遍历所有子节点v，计算每个子节点除当前颜色外的颜色方案数之和。
4.结果计算：根节点的三种颜色方案数之和即为答案。
难点和注意事项
1.树的遍历方向：需先处理子树，再处理父节点，因此使用后序遍历（DFS）。
2.模运算处理：由于方案数可能很大，每次计算后需对 109+710^9+7109+7 取模，避免溢出。
3.已涂色节点限制：已涂色节点的颜色不可更改，需在状态转移时排除冲突颜色。
AC代码（如有雷同，纯属巧合）
复杂度分析
* 时间复杂度：O (N)。每个节点和每条边仅被处理一次，状态转移的颜色枚举为常数时间。
* 空间复杂度：O (N)。主要用于存储树结构和 DP 数组。
该算法通过树形 DP 高效地计算了满足条件的涂色方案数，确保在大规模数据下仍能快速求解。
