fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<int,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. ll ans[300001];
  25. vector<ii> adj[300001];
  26. ll h[300001];
  27. ll sub[300001];
  28. int n; 
  29.  
  30. void dfs(int u, int p)
  31. {
  32. 	sub[u] = 1;
  33. 	for(int i = 0; i < adj[u].size(); i++)
  34. 	{
  35. 		int v = adj[u][i].fi; ll w = adj[u][i].se;
  36. 		if(v==p) continue;
  37. 		h[v] = h[u] + w;
  38. 		dfs(v, u);
  39. 		sub[u] += sub[v];
  40. 	}
  41. }
  42.  
  43. void dfs2(int u, int p)
  44. {
  45. 	for(int i = 0; i < adj[u].size(); i++)
  46. 	{
  47. 		int v = adj[u][i].fi; ll w = adj[u][i].se;
  48. 		if(v==p) continue;
  49. 		ans[v] = ans[u] - w*sub[v] + w*ll(n - sub[v]);
  50. 		dfs2(v, u);
  51. 	}
  52. }
  53.  
  54. int main()
  55. {
  56. 	ios_base::sync_with_stdio(0); cin.tie(0);
  57. 	cin >> n;
  58. 	for(int i = 0; i < n - 1; i++)
  59. 	{
  60. 		int u, v, w;
  61. 		cin>>u>>v>>w;
  62. 		u--; v--;
  63. 		adj[u].pb(mp(v,w));
  64. 		adj[v].pb(mp(u,w));
  65. 	}
  66. 	dfs(0, -1);
  67. 	for(int i = 0; i < n; i++)
  68. 	{
  69. 		ans[0] += h[i];
  70. 	}
  71. 	dfs2(0, -1);
  72. 	for(int i = 0; i < n; i++)
  73. 	{
  74. 		cout << ans[i] << ' ';
  75. 	}
  76. }
  77.  
Success #stdin #stdout 0s 29304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZpY4pN
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!