\(P4084\) \(Barn\) \(Painting\) \(G\)
一、题目描述
给定一颗\(N\)个节点组成的树,\(3\)种颜色,其中\(K\)个节点已染色,要求任意两相邻节点颜色不同,求合法染色方案数。
二、解题思路
树形计数类\(DP\)
状态表示
设\(f[u][j]\)表示将\(u\)染色为\(j\)时,\(u\)这棵子树的方案数
状态转移
\[\large f[u][j]=\prod_{v \in son[u]} \sum_{k \neq j}f[v][k] \]初始化
\(f[u][j]=1\)
特别的,当\(u\)已被染色为\(j\)时,\(f[u][k]=0(k!=t)\)。
答案
\(\large f[1][0]+f[1][1]+f[1][2]\)
小结
树上\(DP\)求方案数的特点是对于\(u\)求出不包含\(u\)的子树方案,因为子树间互不相干,所以将\(u\)的子节点的子树 所有方案之和 乘起来就是 \(u\)子树的方案数 了。对于\(u=root\),就是我们要求的总方案数。请注意其中加法原理和乘法原理的穿插运用。
三、实现代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
const int N = 1e5 + 10, M = N << 1;
int n, m;
int color[N]; // 值域1~3
// 链式前向星
int e[M], h[N], idx, ne[M];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
LL f[N][4]; // 设f[u][j]表示将u染色为j时,u这棵子树的方案数
int st[N]; // 是不是访问过
void dfs(int u) {
st[u] = 1; // 标识已访问
// 初始化
if (color[u])
// 当某个节点被指定上色后,那么该节点另外两种颜色的方案数为0
// 例如:当点u被指定上色2时:f[u][1]=0,f[u][3]=0 (因为无法上色1和3)
f[u][color[u]] = 1;
else
f[u][1] = f[u][2] = f[u][3] = 1; // 三种颜色都可以染
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (st[v]) continue;
dfs(v);
// 对于每个节点,因为不能于子节点上色相同
f[u][1] = (f[u][1] * (f[v][2] + f[v][3]) % mod) % mod;
f[u][2] = (f[u][2] * (f[v][1] + f[v][3]) % mod) % mod;
f[u][3] = (f[u][3] * (f[v][1] + f[v][2]) % mod) % mod;
}
}
int main() {
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
while (m--) {
int u, c;
cin >> u >> c;
color[u] = c; // u节点被染过色,颜色为c
}
dfs(1);
printf("%lld\n", (f[1][1] + f[1][2] + f[1][3]) % mod);
return 0;
}
标签:方案,int,P4084,Painting,节点,Barn
From: https://www.cnblogs.com/littlehb/p/17204104.html