fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <tuple>
  5. using namespace std;
  6.  
  7. int N; vector<pair<int, int> > A[252525], B[252525];
  8. int S[252525]; bool C[252525];
  9. vector<pair<int, long long> > U[252525], L;
  10. long long R[252525];
  11.  
  12. struct min2 {
  13. 	min2() { val[0] = val[1] = { 4e18, -1 }; }
  14. 	pair<long long, int> val[2];
  15. 	void push(pair<long long, int> p) {
  16. 		if (val[0] > p) tie(val[1], val[0]) = tie(val[0], p);
  17. 		else if (val[1] > p) val[1] = p;
  18. 	}
  19. 	long long pop(int y)
  20. 	{
  21. 		return val[val[0].second == y].first;
  22. 	}
  23. }M[252525];
  24.  
  25. void dfs(vector<pair<int, int> >* T, int x, int l, long long d)
  26. {
  27. 	L.emplace_back(x,d);
  28. 	S[x] = 1;
  29. 	for (auto [y, c] : T[x]) if (y != l && !C[y]){
  30. 		dfs(T, y, x, d + c);
  31. 		S[x] += S[y];
  32. 	}
  33. }
  34.  
  35. int center(vector<pair<int, int> >* T, int x)
  36. {
  37. 	L.clear();
  38. 	dfs(T, x, -1, 0);
  39.  
  40. 	int s = L.size();
  41. 	for (auto [y, w] : L) {
  42. 		bool g = 1;
  43. 		for (auto [z, u] : T[y]) if (!C[z]){
  44. 			if (S[y] > S[z] && S[z] * 2 > s) { g = 0; break; }
  45. 			if (S[y] < S[z] && S[y] * 2 < s) { g = 0; break; }
  46. 		}
  47. 		if (g) {
  48. 			L.clear();
  49. 			dfs(T, y, -1, 0);
  50. 			return y;
  51. 		}
  52. 	}
  53. 	return -1;
  54. }
  55.  
  56. void decomp1(int x)
  57. {
  58. 	int c = center(A, x);
  59. 	for (auto [y, w] : L) U[y].emplace_back(c, w);
  60.  
  61. 	C[c] = 1;
  62. 	for (auto [y, w] : A[c]) if (!C[y]) decomp1(y);
  63. 	C[c] = 0;
  64. }
  65.  
  66. void decomp2(int x)
  67. {
  68. 	int c = center(B, x);
  69. 	for (auto [y, w] : L) for (auto [z, u] : U[y]) M[z] = min2();
  70. 	for (auto [y, w] : L) for (auto [z, u] : U[y]) M[z].push({ w + u, y });
  71. 	for (auto [y, w] : L) for (auto [z, u] : U[y]) R[y] = min(R[y], w + u + M[z].pop(y));
  72.  
  73. 	C[c] = 1;
  74. 	for (auto [y, w] : B[c]) if (!C[y]) decomp2(y);
  75. 	C[c] = 0;
  76. }
  77.  
  78. int main()
  79. {
  80. 	scanf ("%d", &N);
  81. 	for (int i = 1; i < N; i++) {
  82. 		int x, y, w; scanf ("%d %d %d", &x, &y, &w);
  83. 		A[x].emplace_back(y, w);
  84. 		A[y].emplace_back(x, w);
  85. 	}
  86. 	for (int i = 1; i < N; i++) {
  87. 		int x, y, w; scanf ("%d %d %d", &x, &y, &w);
  88. 		B[x].emplace_back(y, w);
  89. 		B[y].emplace_back(x, w);
  90. 	}
  91.  
  92. 	decomp1(1);
  93.  
  94. 	for (int i = 1; i <= N; i++) R[i] = 4e18;
  95. 	decomp2(1);
  96. 	for (int i = 1; i <= N; i++) printf ("%lld\n", R[i]);
  97.  
  98. 	return 0;
  99. }
Success #stdin #stdout 0.01s 28596KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/G0GmNs
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!