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

Author Avatar
q234rty 9月 16, 2017

树形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/

隐藏