fork download
copy 
  1. /*
  2.  *  [Ctsc2010]星际旅行.cpp
  3.  *
  4.  *  Created on: 2011-4-19
  5.  *      Author: user
  6.  */
  7.  
  8. #include <cstdio>
  9. #include <iostream>
  10. #include <algorithm>
  11. #include <climits>
  12. #include <cstring>
  13. #include <vector>
  14. #define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
  15. using namespace std;
  16.  
  17. const int MAX_N_VERTEXS = 50000 + 10;
  18.  
  19. struct Vertex {
  20. 	vector<Vertex*> adj;
  21. 	int H;
  22. 	int am[2][2];//normal ,if inc?
  23. 	int chAmSum[2];
  24. 	int ans;
  25. 	int dist;//dist from root to it
  26. 	int am2[2];//it's father chose or not/outside of subtree and it's ancs are inced
  27. 	Vertex*father;
  28. };
  29.  
  30. Vertex vs[MAX_N_VERTEXS];
  31. int nVs;
  32.  
  33. Vertex*que[MAX_N_VERTEXS];
  34.  
  35. void readInput() {
  36. 	cin >> nVs;
  37. 	for (int i = 0; i < nVs; ++i) {
  38. 		scanf("%d", &vs[i].H);
  39. 	}
  40. 	for (int i = 0; i < nVs - 1; ++i) {
  41. 		int a, b;
  42. 		scanf("%d%d", &a, &b);
  43. 		Vertex*u = vs + a, *v = vs + b;
  44. 		u->adj.push_back(v);
  45. 		v->adj.push_back(u);
  46. 	}
  47. }
  48.  
  49. void doBFS(Vertex*root) {
  50. 	int qh = 0, qt = 0;
  51. 	que[qt++] = root;
  52. 	root->father = 0;
  53. 	root->dist = 0;
  54. 	for (; qh < qt;) {
  55. 		Vertex*u = que[qh++];
  56. 		foreach(iter,u->adj) {
  57. 			Vertex*v = *iter;
  58. 			if (v == u->father)
  59. 				continue;
  60. 			que[qt++] = v;
  61. 			v->father = u;
  62. 			v->dist = u->dist + 1;
  63. 		}
  64. 	}
  65. }
  66. void work() {
  67. 	Vertex*root = vs + 0;
  68. 	doBFS(root);
  69.  
  70. 	//calc am
  71. 	for (int at = nVs - 1; at >= 0; --at) {
  72. 		Vertex*u = que[at];
  73. 		for (int cf = 0; cf < 2; ++cf) {
  74. 			for (int inc = 0; inc < 2; ++inc) {
  75. 				int val = u->H + inc;
  76. 				int&ret = u->am[cf][inc];
  77. 				ret = INT_MAX;
  78. 				for (int cme = 0; cme < 2; ++cme) {
  79. 					if (!cf && !cme)
  80. 						continue;
  81. 					int tmp = cme ? val : 0;
  82. 					foreach(iter,u->adj) {
  83. 						Vertex*v = *iter;
  84. 						if (v == u->father)
  85. 							continue;
  86. 						tmp += v->am[cme][0];
  87. 					}
  88. 					ret = min(ret, tmp);
  89. 				}
  90. 			}
  91. 		}
  92. 		for (int c = 0; c < 2; ++c) {
  93. 			u->chAmSum[c] = 0;
  94. 			foreach(iter,u->adj) {
  95. 				Vertex*v = *iter;
  96. 				if (v == u->father)
  97. 					continue;
  98. 				u->chAmSum[c] += v->am[c][0];
  99. 			}
  100. 		}
  101. 	}
  102.  
  103. 	//calc am2
  104. 	root->am2[0] = 0;
  105. 	root->am2[1] = 0;
  106. 	for (int i = 1; i < nVs; ++i) {
  107. 		Vertex*u = que[i];
  108. 		for (int cf = 0; cf < 2; ++cf) {
  109. 			int&ret = u->am2[cf];
  110. 			ret = INT_MAX;
  111. 			for (int cg = 0; cg < 2; ++cg) {
  112. 				if (!cg && !cf)
  113. 					continue;
  114. 				int tmp = 0;
  115. 				if (cf) {
  116. 					if (u->father != vs)
  117. 						tmp += u->father->H + 1;
  118. 					else
  119. 						tmp += u->father->H;
  120. 				}
  121. 				tmp += u->father->am2[cg];
  122. 				tmp += u->father->chAmSum[cf];
  123. 				tmp -= u->am[cf][0];
  124. 				ret = min(ret, tmp);
  125. 			}
  126. 		}
  127. 		//		cout << u->am2[0] << " " << u->am2[1] << endl;
  128. 	}
  129.  
  130. 	//calc ans
  131. 	for (int i = 0; i < nVs; ++i) {
  132. 		Vertex*u = que[i];
  133. 		int&ret = u->ans;
  134. 		ret = INT_MAX;
  135. 		for (int cf = 0; cf < 2; ++cf) {
  136. 			int tmp = 0;
  137. 			tmp += u->am2[cf];
  138. 			if (u == vs)
  139. 				tmp += u->am[cf][0];
  140. 			else
  141. 				tmp += u->am[cf][1];
  142. 			ret = min(ret, tmp);
  143. 		}
  144. 	}
  145.  
  146. 	//output
  147. 	for (int i = 0; i < nVs; ++i) {
  148. 		int ans = vs[i].ans;
  149. 		ans += nVs - 1;
  150. 		ans *= 2;
  151. 		ans -= vs[i].dist;
  152. 		printf("%d\n", ans);
  153. 	}
  154. }
  155.  
  156. void prepare() {
  157. 	for (int i = 0; i < nVs; ++i) {
  158. 		vs[i].H -= vs[i].adj.size();
  159. 	}
  160. }
  161.  
  162. void solve() {
  163. 	readInput();
  164. 	prepare();
  165. 	work();
  166. }
  167.  
  168. int main() {
  169. 	solve();
  170. }
  171.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qzTp2
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!