fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <tuple>
  6. using namespace std;
  7. typedef long long ll;
  8. #define SZ(a) (int)(a).size()
  9.  
  10. vector<vector<tuple<int,int,int>>> al;
  11. vector<vector<pair<ll,int>>> memf;
  12. vector<int> ny;
  13.  
  14.  
  15. pair<ll,int> f (int u, int p) {
  16. 	if (memf[u][p].first != -1) {
  17. 		return memf[u][p];
  18. 	}
  19. 	else if (ny[u] == SZ(al[u])) {
  20. 		auto res = memf[u][SZ(al[u])];
  21. 		auto t = al[u][p];
  22. 		auto res1 = f(get<1>(t), get<2>(t));
  23. 		auto sum = res.first-res1.first-(ll)res1.second*get<0>(t);
  24. 		auto sz = res.second-res1.second;
  25. 		return memf[u][p] = {sum, sz};
  26. 	}
  27. 	else if (ny[u] != -1) {
  28. 		auto res = memf[u][ny[u]];
  29. 		auto t = al[u][ny[u]];
  30. 		auto res1 = f(get<1>(t), get<2>(t));
  31. 		auto sum = res.first+res1.first+(ll)res1.second*get<0>(t);
  32. 		auto sz = res.second+res1.second;
  33. 		memf[u][SZ(al[u])] = {sum, sz};
  34. 		ny[u] = SZ(al[u]);
  35. 		return f(u, p);
  36. 	}
  37. 	else {
  38. 		ll sum = 0;
  39. 		int sz = 1; 
  40. 		for (int i = 0; i < SZ(al[u]); i++) if (i != p) {
  41. 			auto t = al[u][i];
  42. 			auto res = f(get<1>(t), get<2>(t));
  43. 			sum += res.first+(ll)res.second*get<0>(t);
  44. 			sz += res.second;
  45. 		}
  46. 		ny[u] = p;
  47. 		return memf[u][p] = {sum, sz};
  48. 	}
  49. }
  50.  
  51. int main() {
  52. 	cin.sync_with_stdio(false);
  53. 	int n;
  54. 	cin >> n;
  55. 	al.assign(n, {});
  56. 	for (int i = 0; i < n-1; i++) {
  57. 		int u, v, w;
  58. 		cin >> u >> v >> w;
  59. 		u--;
  60. 		v--;
  61. 		auto su = SZ(al[u]);
  62. 		auto sv = SZ(al[v]);
  63. 		al[u].emplace_back(w, v, sv);
  64. 		al[v].emplace_back(w, u, su);
  65. 	}
  66. 	memf.resize(n);
  67. 	for (int u = 0; u < n; u++) {
  68. 		memf[u].assign(SZ(al[u])+1, {-1, -1});
  69. 	}
  70. 	ny.assign(n, -1);
  71. 	for (int u = 0; u < n; u++) {
  72. 		printf("%lld%c", f(u, SZ(al[u])).first, " \n"[u == n-1]);
  73. 	}
  74. 	return 0;
  75. }
  76.  
Runtime error #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Y1VDFC
language:
C++14 (gcc 8.3)
created:
7 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!