一、题目大意给一棵n个节点的树结点编号从1~n。对树进行染色一共有3种颜色每个结点只能从3种颜色中取一种进行染色有边相连的两个结点不能染同一种颜色。给定部分节点的颜色问有多少种染色方式二、简单思路对树做dfs搜索每个结点的颜色情况再统计总方案数。这种思路可以拿部分分但肯定不是正解。题目问的是总方案数并不需要把每种方案都列举出来这么做肯定会超时。三、正解上面已经说到我们只要统计总方案数即可每一个节点的颜色只会影响到它子结点的方案数所以我们可以用树上dp。1.dp数组的定义定义dp[u][c]表示以u为根的子树当u的颜色为c时产生的染色总方案数。每次搜索u的子节点v将v染成和c不同的两种颜色。不难发现和c不同的两种颜色分别为 (c%31) 和 ( (c1)%31 )。2.dp顺序按照对树进行dfs的顺序。3.状态转移方程对于以u为根的子树当u的颜色为c时对于u的每个子节点vv的子树有(dp[v][c1]dp[v][c2]) 种染色方案数。其中c1c2为与c不同的两种颜色即c1 c%31c2 (c1)%31。所以dp[u][c] dp[u][c] *(其中v为u的子节点c1c2为与c不同的两种颜色注意dp[u][c]初始值为1但有特殊情况下文会补充说明。4.特判当u的颜色已给出我们假设其为k那就直接把dp[u][k]设为1 其他颜色全都设为0。最后输出dp[1][1]dp[1][2]dp[1][3]即可(为了方便默认1为树根)。四、完整代码#includebits/stdc.h #define int long long using namespace std; const int N 1e5 7; const int MOD 1e9 7; int n, k; int dp[N][4]; vectorint G[N]; int color[N]; void dfs(int u, int fa) { dp[u][1] dp[u][2] dp[u][3] 1; if(color[u]) { int c color[u]; int c1 c%31, c2 (c1)%31; dp[u][c1] dp[u][c2] 0; } for(auto v : G[u]) { if(v fa) continue; dfs(v, u); for(int c1;c4;c) { int c1 c%31, c2 (c1)%31; dp[u][c] dp[u][c] * ((dp[v][c1] dp[v][c2]) % MOD) % MOD; } } } signed main() { cinnk; for(int i1;in;i) { int u, v; cinuv; G[u].push_back(v); G[v].push_back(u); } for(int i1;ik;i) { int b, c; cinbc; color[b] c; } dfs(1,0); cout(dp[1][1] dp[1][2] dp[1][3]) % MOD; return 0; }(本人今年初二如果本文有什么错误望各位大佬指出