【树形计数DP】P4084 [USACO17DEC]Barn Painting G

╰+攻爆jí腚メ 2024-03-16 19:25 100阅读 0赞

P4084 [USACO17DEC]Barn Painting G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意:

a141bb2bae1b4445bb33c6acda7e6e59.png

思路:

简单树形DP题,应该要会的

树上染色,且颜色一共就3种,很自然地想到这样设计:

dp[u][j]表示以u为根的子树,结点u涂成颜色j的方案数

转移的时候容易想不清楚,其实就是乘法原理,想成一列,然后类似于二分图连边的感觉,就行了

Code:

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int mxn=1e5+10;
  5. const int mxe=1e5+10;
  6. const int mod=1e9+7;
  7. struct ty{
  8. int to,next;
  9. }edge[mxe<<2];
  10. int N,K,x,c;
  11. int u,v,tot=0;
  12. int head[mxn];
  13. int dp[mxn][4],col[mxn];
  14. void add(int u,int v){
  15. edge[tot].to=v;
  16. edge[tot].next=head[u];
  17. head[u]=tot++;
  18. }
  19. void G_init(){
  20. tot=0;
  21. for(int i=0;i<=N;i++){
  22. head[i]=-1;
  23. }
  24. }
  25. void dfs(int u,int fa){
  26. if(!col[u]) dp[u][1]=dp[u][2]=dp[u][3]=1;
  27. else dp[u][col[u]]=1;
  28. for(int i=head[u];~i;i=edge[i].next){
  29. if(edge[i].to==fa) continue;
  30. dfs(edge[i].to,u);
  31. dp[u][1]*=(dp[edge[i].to][2]+dp[edge[i].to][3])%mod,dp[u][1]%=mod;
  32. dp[u][2]*=(dp[edge[i].to][1]+dp[edge[i].to][3])%mod,dp[u][2]%=mod;
  33. dp[u][3]*=(dp[edge[i].to][1]+dp[edge[i].to][2])%mod,dp[u][3]%=mod;
  34. }
  35. }
  36. void solve(){
  37. cin>>N>>K;
  38. G_init();
  39. for(int i=1;i<=N-1;i++){
  40. cin>>u>>v;
  41. add(u,v);
  42. add(v,u);
  43. }
  44. for(int i=1;i<=K;i++){
  45. cin>>x>>c;
  46. col[x]=c;
  47. }
  48. dfs(1,0);
  49. cout<<(dp[1][1]+dp[1][2]+dp[1][3])%mod<<'\n';
  50. }
  51. signed main(){
  52. ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  53. int __=1;//cin>>__;
  54. while(__--)solve();return 0;
  55. }

发表评论

表情:
评论列表 (有 0 条评论,100人围观)

还没有评论,来说两句吧...

相关阅读

    相关 Paint 详解

    尊重原创,[转载请标明出处][Link 1]    [http://blog.csdn.net/abcdef314159][Link 1] 自定义控件具有很强的灵活性,可以根