fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int maxn = 2e5+5;
  5. vector<pair<int,int>> g[maxn];
  6. int child[maxn];
  7. int ans[maxn];
  8. void dfs(int node, int parent, int fix, int val){
  9. 	if(child[node] == -1){
  10. 		ans[fix] = min(ans[fix],val);
  11. 		return;
  12. 	}
  13. 	for(auto m: g[node]){
  14. 		int i = m.first,num = m.second;
  15. 		if(i == parent){
  16. 			continue;
  17. 		}
  18. 		if(i == child[node]){
  19. 			dfs(i,node,fix,val+num);
  20. 		}
  21. 		else{
  22. 			dfs(i,node,fix+1,val+num);
  23. 		}
  24. 	}
  25. }
  26. signed main() {
  27. 	int N; cin>>N;
  28. 	for(int i = 1;i<=N-1;i++){
  29. 		int a,b,c; cin>>a>>b>>c;
  30. 		g[a].push_back(make_pair(b,c));
  31. 		g[b].push_back(make_pair(a,c));
  32. 	}
  33. 	for(int i =0;i<=N;i++){
  34. 		ans[i] = 1e18;
  35. 	}
  36. 	for(int i =1;i<=N;i++){
  37. 		int a; cin>>a;
  38. 		if(a == 0) child[i] = -1;
  39. 		else child[i] = a;
  40. 		// cout<<child[i]<<" ";
  41. 	}
  42. 	dfs(1,-1,0,0);
  43. 	for(int i = 1;i<=N-1;i++){
  44. 		ans[i] = min(ans[i],ans[i-1]);
  45. 	}
  46. 	for(int i = 0;i<N;i++) cout<<ans[i]<<endl;
  47. 	return 0;
  48. }
Success #stdin #stdout 0.01s 10892KB
comments (?)
stdin
copy 
8
 1 2 3
 2 3 2
 2 4 9
 3 5 1
 1 6 49
 6 7 8
 3 8 5
 6 4 8 0 0 7 0 0
stdout
copy 
57
12
10
6
6
6
6
6
https://ideone.com/wUWHnl
language:
C++14 (gcc 8.3)
created:
42 days 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!