?給樹的點染色，顏色有3種，相鄰的點顏色不同

某些點已經染色

方案數？

#include <bits/stdc++.h>using namespace std ;const int N=1e5+2,M=5*N;#define int long longconst int mod=1e9+7;int f[N][4],n;int nxt[M],go[M],hd[N],all;void add(int x,int y){go[++all]=y,nxt[all]=hd[x];hd[x]=all;}void dfs(int x,int fa){int i;for(i=1;i<=3;i++){ if(f[x][i]){for(int j=1;j<i;j++) f[x][j]=0;break;} f[x][i]=1;}for(i=hd[x];i;i=nxt[i]){int y=go[i]; if(y==fa) continue; dfs(y,x);f[x][1]=f[x][1]*(f[y][2]+f[y][3]);f[x][2]=f[x][2]*(f[y][1]+f[y][3]);f[x][3]=f[x][3]*(f[y][1]+f[y][2]);f[x][1]%=mod;f[x][2]%=mod;f[x][3]%=mod;}}signed main(){int i,x,y,K;cin>>n>>K;for(i=1;i<n;i++) cin>>x>>y,add(x,y),add(y,x);for(i=1;i<=K;i++) cin>>x>>y,f[x][y]=1;dfs(1,0);cout<<(f[1][1]+f[1][2]+f[1][3])%mod<<endl;}

總結

以上是生活随笔為你收集整理的luogu 4084的全部內容，希望文章能夠幫你解決所遇到的問題。

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