[关闭]
@ysner 2018-10-11T15:01:50.000000Z 字数 1099 阅读 304

[CQOI2009]叶子的染色

DP 树形DP


题面

戳我

解析

一开始脑抽了,状态转移时默认直接在子结点染色。。。
其实这道题还是很简单的。
表示子树内的叶子结点还需要颜色,或都不需要颜色。
然后直接转移就对了。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=1e4+100;
  14. int n,m,h[N],cnt,w[N],dp[3][N];
  15. struct Edge{int to,nxt;}e[N<<1];
  16. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  17. il ll gi()
  18. {
  19. re ll x=0,t=1;
  20. re char ch=getchar();
  21. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  22. if(ch=='-') t=-1,ch=getchar();
  23. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  24. return x*t;
  25. }
  26. il void dfs(re int u,re int fa)
  27. {
  28. if(u<=m) dp[2][u]=1,dp[!w[u]][u]=1e5;
  29. for(re int i=h[u];i+1;i=e[i].nxt)
  30. {
  31. re int v=e[i].to;
  32. if(v==fa) continue;
  33. dfs(v,u);
  34. dp[0][u]+=min(dp[0][v],dp[2][v]);
  35. dp[1][u]+=min(dp[1][v],dp[2][v]);
  36. dp[2][u]+=dp[2][v];
  37. }
  38. dp[2][u]=min(dp[2][u],min(dp[1][u],dp[0][u])+1);
  39. }
  40. int main()
  41. {
  42. memset(h,-1,sizeof(h));
  43. n=gi();m=gi();
  44. fp(i,1,m) w[i]=gi();
  45. fp(i,1,n-1)
  46. {
  47. re int u=gi(),v=gi();
  48. add(u,v);add(v,u);
  49. }
  50. dfs(n,0);
  51. printf("%d\n",dp[2][n]);
  52. return 0;
  53. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注