正題

題目鏈接:https://www.luogu.org/problemnew/show/P3914

---

題目大意

$n$個點每個點有些可以染的顏色，要求相鄰顏色不相同，方案總數。

---

解題思路

樹形$dp$，定義$f_{x,i}$表示點$x$的染顏色$i$的方案數。然后定義$z_x={\sum }_{i=1}^m{f}_{x_i}$

然后顯然動態轉移方程$$f_{x,i}=z_y?f_{y,i}(x?>y)$$

---

$code$

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int XJQ=1e9+7,N=5001; int tot,n,m,f[N][N],z[N],ls[N]; struct node{int to,next; }a[2*N]; void addl(int x,int y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dp(int x,int fa) {for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa) continue;dp(y,x);int k=1;for(int j=1;j<=m;j++)f[x][j]=1ll*f[x][j]*((z[y]-f[y][j]+XJQ)%XJQ)%XJQ;}for(int j=1;j<=m;j++)(z[x]+=f[x][j])%=XJQ; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int k,x;scanf("%d",&k);for(int j=1;j<=k;j++)scanf("%d",&x),f[i][x]=1;}for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}dp(1,0);printf("%d",z[1]); }

總結

以上是生活随笔為你收集整理的P3914-染色计数【树形dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。