fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define S second
  3. #define F first 
  4. #define PB push_back
  5. using namespace std;
  6. int const N=1e6+1;
  7. bool odw[N];
  8. int PD[N],t[N];
  9. long long DR[N], MA2[N];
  10. pair<long long,int>MA1[N];
  11. vector<pair<int,int>>g[N];
  12.  
  13. void dfs(int v){
  14. 	odw[v]=1;
  15. 	//cout<<v;
  16. 	for(pair<int,int> i:g[v]){
  17. 		if(odw[i.F]==0) {
  18. 			dfs(i.F);
  19. 		PD[v]+=PD[i.F];
  20. 		if(PD[i.F]!=0) DR[v]+=DR[i.F]+i.S;
  21. 		if(MA1[v].F<=MA1[i.F].F+i.S&&PD[i.F]!=0){
  22. 			MA2[v]=MA1[v].F;
  23. 			MA1[v].F=MA1[i.F].F+i.S;
  24. 			MA1[v].S=i.F;
  25. 		}
  26. 		else if(MA2[v]<MA1[i.F].F+i.S&&PD[i.F]!=0) MA2[v]=MA1[i.F].F+i.S;
  27. 	}
  28. 		//if(v==2) cout<<PD[v];
  29. 	}
  30. }
  31.  
  32. void dfs2(int v){
  33. 	odw[v]=1;
  34. 	for(pair<int,int> i:g[v]){
  35. 		if(odw[i.F]==0){
  36. 			if(PD[i.F]!=PD[v]){
  37. 				DR[i.F]=DR[v];
  38. 				if(PD[i.F]==0) DR[i.F]+=i.S;
  39. 				if(MA1[v].S==i.F){
  40. 					if(MA2[v]+i.S>MA1[i.F].F){
  41. 						MA2[i.F]=MA1[i.F].F;
  42. 						MA1[i.F].F=MA2[v]+i.S;
  43. 						MA1[i.F].S=v;
  44. 					}
  45. 					else if(MA2[v]+i.S>MA2[i.F]) MA2[i.F]=MA2[v]+i.S;
  46. 				}
  47. 				else {
  48. 					if(MA1[v].F+i.S>MA1[i.F].F){
  49. 						MA2[i.F]=MA1[i.F].F;
  50. 						MA1[i.F].F=MA1[v].F+i.S;
  51. 						MA1[i.F].S=v;
  52. 					}
  53. 					else if(MA1[v].F+i.S>MA2[i.S]) MA2[i.S]=MA1[v].F+i.S;
  54. 				}
  55.  
  56. 				PD[i.F]=PD[v];
  57.  
  58. 			}
  59. 			t[i.F]=2*DR[i.F]-MA1[i.F].F;
  60. 			 dfs2(i.F);
  61.  
  62. 		}
  63. 	}
  64. }
  65.  
  66. int main() {
  67. 	ios_base::sync_with_stdio(0);
  68. 	cin.tie(0);
  69. 	int n,m,u,v,w;
  70. 	cin>>n>>m;
  71. 	for(int i=1;i<n;i++){
  72. 		cin>>u>>v>>w;
  73. 		g[u].PB({v,w});
  74. 		g[v].PB({u,w});
  75. 	}
  76. 	for(int i=0;i<m;i++){
  77. 		cin>>u;
  78. 		PD[u]++;
  79. 	}
  80. 	dfs(1);
  81. 	for(int i=1;i<=n;i++) odw[i]=0;
  82. 	t[1]=2*DR[1]-MA1[1].F;
  83. 	dfs2(1);
  84. 	for(int i=1;i<=n;i++) cout<<t[i]<<"\n";
  85. 	//cout<<2*DR[1]-MA1[1].F;
  86. }
Success #stdin #stdout 0.01s 35872KB
comments (?)
stdin
copy 
5 2
2 5 1
2 4 1
1 2 2
1 3 2
4 5
stdout
copy 
5
3
7
2
2
https://ideone.com/lbPgjh
language:
C++ (gcc 8.3)
created:
11 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!