[关闭]
@ysner 2018-10-03T16:06:44.000000Z 字数 1475 阅读 1779

[CF348B]Apple Tree

DP 树形DP


题面

给一棵大小为的树,树的每个叶子节点上有权值。
定义一颗树平衡:对于每一个结点的子树都拥有相同的权值之和。
问至少要减掉多少权值才能使树平衡。

解析

这题想了半天。。。

一开始的想法是一遍,回溯时每个点把其所有子树减到其最小子树大小。
然而立即发现我是个**,这会影响子树内的平衡。

如果把一个点的权值定义为它子树内的权值和,
在一个子树内,所有的点都减去同一个值,才不会影响其平衡。
所以如果要在一个点减小其权值,一减就要减它所有儿子权值的

为了使当前点平衡,我们需要使其所有子树大小相等。
为了使以后修改时仍然平衡,当然要使所有子树大小都为的倍数。
如果一个儿子大小小于,说明不能保留子树。

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