洛谷P4084 [USACO17DEC]Barn Painting G 題解

題目鏈接：P4084 [USACO17DEC]Barn Painting G

題意：題意：給定一顆N個(gè)節(jié)點(diǎn)組成的樹(shù)，3種顏色，其中K個(gè)節(jié)點(diǎn)已染色，要求任意兩相鄰節(jié)點(diǎn)顏色不同，求合法染色方案數(shù)。

這個(gè)題太水了

設(shè) $dp[u][1/2/3]$ 表示 $u$ 結(jié)點(diǎn)涂 $1/2/3$ 顏色的方案數(shù)

根據(jù)加法原理，

如果 $u$ 已經(jīng)有顏色了，那么
$$dp[u][j]=\sum dp[v][k]\times [k=j]\times [j=\text{val[u]}]$$
否則
$$dp[u][j]=\sum dp[v][k]\times [k=j]$$
時(shí)間復(fù)雜度 $O(n)$

代碼：

#include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1e5+15) const int p=1e9+7; int n,k; int val[N],dp[N][4]; vector<int> vec[N]; void add(int &a,int b){a=(a+b%p)%p;} void mul(int &a,int b){a=a%p*b%p;} void dfs(int u,int f) {for(int v : vec[u]){if(v==f)continue;dfs(v,u);for(int i=1; i<=3; i++){int res=0;for(int j=1; j<=3; j++)if(i!=j)add(res,dp[v][j]);mul(dp[u][i],res);}} } signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// freopen("check.in","r",stdin);// freopen("check.out","w",stdout);cin >> n >> k;for(int i=1,u,v; i<n; i++){cin >> u >> v;vec[u].push_back(v);vec[v].push_back(u);}for(int i=1; i<=n; i++)for(int j=1; j<=3; j++)dp[i][j]=1;for(int i=1,u; i<=k; i++){cin >> u >> val[u];for(int j=1; j<=3; j++)if(val[u]!=j)dp[u][j]=0;}dfs(1,1);cout << ((dp[1][1]+dp[1][2]+dp[1][3])%p+p)%p << endl;return 0; }

轉(zhuǎn)載請(qǐng)說(shuō)明出處

總結(jié)

以上是生活随笔為你收集整理的洛谷P4084 [USACO17DEC]Barn Painting G 题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。