【BZOJ1827】【Vijos1487】【Usaco2010 Mar】奶牛聚会

树形DP即可。

我们定义 \displaystyle f(u)=\sum_{v \text{ in }u\text{'s subtree} } c_v \times dis(u,v) \displaystyle g(u)=\sum_{v \text{ isn't in }u\text{'s subtree} } c_v \times dis(u,v)

那么 \displaystyle ans=\min_{1\le u \le n}f(u)+g(u)

接下来考虑怎么求 f g

容易发现 \displaystyle f(u)=\sum_{v\text{ is }u\text{'s child}}f(v)+w(u,v)*sz(v) ,其中 \displaystyle sz(u)=\sum_{v \text{ in }u\text{'s subtree} } c_v

那么 g(u) 怎么求呢?考虑从 g(fa(u))+f(fa(u)) 里减去 u 的子树的贡献,设 \displaystyle sum=\sum_{u=1}^{n} c_u ,我们有:

g(u)=f(fa(u))+g(fa(u))-f(u)-sz(u)*w(u,fa(u))+(sum-sz(u))\times w(u,fa(u))

于是两遍dfs计算 sz f g 就好。

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=30000020;
  5. const ll INF=0x3f3f3f3f3f3f3f3fLL;
  6. int bufpos;
  7. char buf[MAXSIZE];
  8. #define NEG 0
  9. void init(){
  10. #ifdef LOCAL
  11. freopen("1827.txt","r",stdin);
  12. #endif
  13. buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  14. bufpos=0;
  15. }
  16. #if NEG
  17. int readint(){
  18. bool isneg;
  19. int val=0;
  20. for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  21. bufpos+=(isneg=buf[bufpos]=='-');
  22. for(;isdigit(buf[bufpos]);bufpos++)
  23. val=val*10+buf[bufpos]-'0';
  24. return isneg?-val:val;
  25. }
  26. #else
  27. int readint(){
  28. int val=0;
  29. for(;!isdigit(buf[bufpos]);bufpos++);
  30. for(;isdigit(buf[bufpos]);bufpos++)
  31. val=val*10+buf[bufpos]-'0';
  32. return val;
  33. }
  34. #endif
  35. char readchar(){
  36. for(;isspace(buf[bufpos]);bufpos++);
  37. return buf[bufpos++];
  38. }
  39. int readstr(char* s){
  40. int cur=0;
  41. for(;isspace(buf[bufpos]);bufpos++);
  42. for(;!isspace(buf[bufpos]);bufpos++)
  43. s[cur++]=buf[bufpos];
  44. s[cur]='\0';
  45. return cur;
  46. }
  47. const int maxn=100001;
  48. struct graph{
  49. ll sum;
  50. int n,m;
  51. struct edge{
  52. int to,next,cost;
  53. }e[maxn*2];
  54. int first[maxn];
  55. void addedge(int from,int to,int cost){
  56. e[++m]=(edge){to,first[from],cost};
  57. first[from]=m;
  58. }
  59. bool vis[maxn];
  60. ll c[maxn],sz[maxn];
  61. ll f[maxn],g[maxn];
  62. void dfs(int u){
  63. sz[u]=c[u];
  64. vis[u]=1;
  65. for(int i=first[u];i;i=e[i].next){
  66. int v=e[i].to;
  67. if (vis[v])
  68. continue;
  69. dfs(v);
  70. sz[u]+=sz[v];
  71. f[u]+=f[v]+sz[v]*e[i].cost;
  72. }
  73. }
  74. void dfs2(int u){
  75. vis[u]=1;
  76. //printf("%d\n",u);
  77. for(int i=first[u];i;i=e[i].next){
  78. int v=e[i].to;
  79. //printf("%d\n",v);
  80. if (vis[v])
  81. continue;
  82. g[v]=g[u]+f[u]-f[v]-sz[v]*e[i].cost+(sum-sz[v])*e[i].cost;
  83. dfs2(v);
  84. }
  85. }
  86. ll work(int n){
  87. for(int i=1;i<=n;i++)
  88. sum+=c[i];
  89. dfs(1);
  90. memset(vis,0,sizeof(vis));
  91. dfs2(1);
  92. ll ans=INF;
  93. for(int i=1;i<=n;i++){
  94. //printf("%lld %lld %lld\n",sz[i],f[i],g[i]);
  95. ans=min(ans,f[i]+g[i]);
  96. }
  97. return ans;
  98. }
  99. }g;
  100. int main(){
  101. init();
  102. int n=readint();
  103. for(int i=1;i<=n;i++)
  104. g.c[i]=readint();
  105. for(int i=1;i<n;i++){
  106. int x=readint(),y=readint(),z=readint();
  107. g.addedge(x,y,z);
  108. g.addedge(y,x,z);
  109. }
  110. printf("%lld",g.work(n));
  111. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

本文链接:https://www.q234rty.top/2017/09/16/bzoj1827/

隐藏