fork download
copy 
  1. // first second push_back unordered return continue break vector visited check flag bool while iterator begin end lower_bound upper_bound temp true false ll_MAX ll_MIN insert erase clear pop push compare ll64_MAX ll64_MIN  reverse replace stringstream string::npos length substr front priority_queue
  2.  
  3. #ifndef ONLINE_JUDGE
  4. #include "debug.h"
  5. #else
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. #define debug(...) 42
  9. #endif
  10.  
  11. #define endl '\n'
  12. #define ll long long
  13. #define rint register int
  14. #define minpq priority_queue <int, vector<int>, greater<int> >
  15. #define maxpq  priority_queue <int>
  16.  
  17. #define re register
  18. #define pb(x) push_back(x);
  19. #define ce(x) cout << x << '\n';
  20.  
  21. using db = long double;
  22. using pll = pair < ll, ll >;
  23. #define scan(a, n) 		for(int i = 0; i < n; i++)cin >> a[i];
  24.  
  25. #define rep(i,x,n,inc) for(int i=x ; i<n ; i+=inc)
  26. #define repr(i,x,n,inc) for( i=x ; i>n ; i+=inc)
  27. #define all(a)      (a).begin(),(a).end()
  28. #define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))
  29.  
  30. #define mp(a,b) make_pair(a,b)
  31. #define ff first
  32. #define ss second
  33. #define hell 1000000007
  34. #define infl 1000000007
  35.  
  36. #define conutBits(n)	__builtin_popcount(n)
  37. #define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
  38. #define Fill(s,v) memset(s,v,sizeof(s))
  39. #define cout_p(x, p) cout << fixed << setprecision((p)) << x << endl     //print with precision
  40.  
  41. void test_case() {
  42. 	ll n, m, q;
  43. 	cin >> n;
  44. 	vector<pll> v[n + 1], query[n + 1];
  45.  
  46. 	for (int i = 0; i < n - 1; i++) {
  47. 		ll x, y, w;
  48. 		cin >> x >> y >> w;
  49. 		v[x].push_back({y, w});
  50. 		v[y].push_back({x, w});
  51. 	}
  52.  
  53. 	vector<ll> ans(n + 1, 0), sub(n + 1, 0), pre(n + 1, 0);
  54.  
  55. 	function<void(ll, ll)> dfs = [&](ll s, ll p) {
  56. 		sub[s] = 0;
  57.  
  58. 		for (auto zx : v[s]) {
  59. 			if (zx.ff != p) {
  60. 				dfs(zx.ff, s);
  61. 				// debug(s, zx.ss + sub[zx.ff]);
  62. 				if (zx.ss + sub[zx.ff] >= sub[s]) {
  63. 					pre[s] = sub[s];
  64. 					sub[s] = zx.ss + sub[zx.ff];
  65. 				} else if (zx.ss + sub[zx.ff] >= pre[s]) {
  66. 					pre[s] = zx.ss + sub[zx.ff];
  67. 				}
  68. 			}
  69. 		}
  70. 	};
  71.  
  72.  
  73. 	function<void(ll, ll, ll)> bfs = [&](ll s, ll p, ll up) {
  74. 		if (s != 1) {
  75. 			debug(s);
  76.  
  77. 			for (auto zx : v[s]) {
  78. 				if (zx.ff != p) {
  79. 					sub[zx.ff] = max(sub[zx.ff], zx.ss + up);
  80.  
  81. 					debug(zx.ff, s, zx.ss + up);
  82. 					bfs(zx.ff, s, zx.ss + up);
  83. 				}
  84. 			}
  85. 		} else {
  86. 			for (auto zx : v[s]) {
  87. 				if (zx.ff != p) {
  88. 					if (zx.ss + sub[zx.ff] == sub[s]) {
  89. 						sub[zx.ff] = max(sub[zx.ff], zx.ss + pre[s]);
  90.  
  91. 						debug(zx.ff, s, zx.ss + pre[s]);
  92. 						bfs(zx.ff, s, zx.ss + pre[s]);
  93. 					} else {
  94. 						sub[zx.ff] = max(sub[zx.ff], zx.ss + sub[s]);
  95.  
  96. 						debug(zx.ff, s, zx.ss + sub[s]);
  97. 						bfs(zx.ff, s, zx.ss + sub[s]);
  98. 					}
  99. 				}
  100. 			}
  101. 		}
  102. 		// 12 9 7 12
  103. 	};
  104.  
  105. 	dfs(1, -1);
  106. 	bfs(1, -1, 0);
  107.  
  108. 	for (int i = 1; i < n + 1; i++)
  109. 		cout << sub[i] << ' ';
  110. 	cout << "\n";
  111.  
  112. 	debug(sub, pre);
  113. }
  114.  
  115. int32_t main() {
  116. 	ios_base::sync_with_stdio(false);
  117. 	cin.tie(NULL); cout.tie(NULL);
  118. 	ll tc;
  119. 	cin >> tc;
  120. 	while (tc--)
  121. 		test_case();
  122. 	return 0;
  123. }
  124.  
Runtime error #stdin #stdout 0s 4252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NTO3oZ
language:
C++14 (gcc 8.3)
created:
4 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!