fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	std::ios_base::sync_with_stdio(false);
  6. 	int n; cin >> n;
  7. 	vector<int64_t> w(n+1);
  8. 	int64_t tw = 0;
  9. 	for (int i = 1; i <= n; ++i) {
  10. 		cin >> w[i]; tw += w[i];
  11. 	}
  12. 	vector<vector<int>> adj(n+1);
  13. 	for (int i = 1; i <= n - 1; ++i) {
  14. 		int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u);
  15. 	}
  16. 	vector<int64_t> pw(n+1);
  17. 	vector<pair<int, int>> etime(n+1);
  18. 	vector<int> etour;
  19. 	function<int64_t(int, int)> dfs1 = [&] (int u, int from) {
  20. 		int enter = etour.size();
  21. 		etour.push_back(u);
  22. 		int64_t ans = w[u];
  23. 		for (auto v : adj[u]) if (v != from) ans += dfs1(v, u);
  24. 		int left = etour.size();
  25. 		etime[u] = {enter, left};
  26. 		pw[u] = tw - ans;
  27. 		return ans;
  28. 	};
  29. 	dfs1(1, -1);
  30. 	vector<vector<int>> sub(n * 4 + 1);
  31. 	auto etour_cmp = [&] (int u, int v) { return pw[u] < pw[v]; };
  32. 	function<int(int, int, int)> build = [&] (int l, int r, int k) {
  33. 		vector<int>& sorted = sub[k];
  34. 		if (r - l > 1) {
  35. 			int m = l + (r - l) / 2;
  36. 			vector<int>&lsorted = sub[build(l, m, k * 2)];
  37. 			vector<int>&rsorted = sub[build(m, r, k * 2 + 1)];
  38. 			merge(
  39. 				lsorted.begin(), lsorted.end(),
  40. 				rsorted.begin(), rsorted.end(),
  41. 				back_inserter(sorted), etour_cmp
  42. 			);
  43. 		} else {
  44. 			sorted.insert(sorted.end(), etour.begin()+l, etour.begin()+r);
  45. 		}
  46. 		return k;
  47. 	};
  48. 	int k = build(0, etour.size(), 1);
  49. 	int64_t ans = 2 * tw; // worst case - triplicate the tree
  50.  
  51. 	function<int(vector<int>&,int)> find_closest_helper = [&] (vector<int>& arr, int64_t hw) {
  52. 		int l = 0, r = arr.size();
  53. 		int64_t best = -1;
  54. 		int best_idx;
  55. 		while (l < r) {
  56. 			int m = l + (r - l) / 2;
  57. 			if (best == -1 || std::abs(2 * pw[arr[m]] - hw) < best) {
  58. 				best = std::abs(2 * pw[arr[m]] - hw);
  59. 				best_idx = m;
  60. 			}
  61. 			if (2 * pw[arr[m]] < hw)
  62. 				l = m + 1;
  63. 			else
  64. 				r = m;
  65. 		}
  66. 		return arr[best_idx];
  67. 	};
  68.  
  69. 	function<int(int, int, int64_t, int, int, int)> find_closest = [&] (int l, int r, int64_t hw, int tl, int tr, int tk) {
  70. 		l = max(l, tl);
  71. 		r = min(r, tr);
  72. 		if (l >= r) {
  73. 			return -1;
  74. 		}
  75. 		if (l == tl && r == tr) {
  76. 			return find_closest_helper(sub[tk], hw);
  77. 		}
  78. 		int tm = tl + (tr - tl) / 2;
  79. 		int lans = find_closest(l, r, hw, tl, tm, tk * 2);
  80. 		int rans = find_closest(l, r, hw, tm, tr, tk * 2 + 1);
  81. 		if (lans == -1) return rans;
  82. 		if (rans == -1) return lans;
  83. 		if (std::abs(2 * pw[lans] - hw) < std::abs(2 * pw[rans] - hw))
  84. 			return lans;
  85. 		return rans;
  86. 	};
  87.  
  88. 	for (int u = 1; u <= n; ++u) {
  89. 		// we cut away node u and obtain a tree of weight a and its parent is (tw - a)
  90. 		int64_t a = tw - pw[u];
  91.  
  92. 		// now we need to find vertex v such that
  93. 		// max(pw[v] - a, tw - pw[v]) is minimal
  94. 		// a <= pw[v] <= tw
  95. 		// so we need to find v s.t. 2 * pw[v] is closest to (a + tw)
  96.  
  97. 		pair<int, int> atime = etime[u];
  98.  
  99. 		// we ignore all vertices in u subtree
  100. 		int v1 = find_closest(0, atime.first, a + tw, 0, etour.size(), 1);
  101. 		int v2 = find_closest(atime.second, etour.size(), a + tw, 0, etour.size(), 1);
  102.  
  103. 		auto evaluate = [&] (int v) -> int64_t {
  104. 			int64_t b = pw[v] - a;
  105. 			int64_t c = tw - a - b;
  106. 			return 3 * max(a, max(b, c)) - a - b - c;
  107. 		};
  108.  
  109. 		for (auto v : vector<int>{v1, v2}) {
  110. 			if (v == -1) continue;
  111. 			ans = min(ans, evaluate(v));
  112. 		}
  113. 	}
  114.  
  115. 	cout << ans << endl;
  116. }
  117.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
5
1 2 2 1 1
1 2
1 3
3 5
1 4
stdout
copy 
2
https://ideone.com/zNvYoi
language:
C++14 (gcc 8.3)
created:
8 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!