fork(1) 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(PD[i.F]-PD[v]!=0){
  36. 			DR[i.F]=DR[v];
  37. 			if(MA1[v].S==i.F){
  38. 				if(MA2[v]+i.S>MA1[i.F].F){
  39. 					MA2[i.F]=MA1[i.F].F;
  40. 					MA1[i.F].F=MA2[v]+i.S;
  41. 					MA1[i.F].S=v;
  42. 				}
  43. 				else if(MA2[v]+i.S>MA2[i.F]) MA2[i.F]=MA2[v]+i.S;
  44. 			}
  45. 			else {
  46. 				if(MA1[v].F+i.S>MA1[i.F].F){
  47. 					MA2[i.F]=MA1[i.F].F;
  48. 					MA1[i.F].F=MA1[v].F+i.S;
  49. 					MA1[i.F].S=v;
  50. 				}
  51. 				else if(MA1[v].F+i.S>MA2[i.S]) MA2[i.S]=MA1[v].F+i.S;
  52. 			}
  53. 			PD[i.F]=PD[v];
  54. 			t[i.F]=2*DR[i.F]-MA1[i.F].F;
  55. 		}
  56. 		else {
  57. 			t[i.F]=2*DR[v]+i.S-MA1[v].F;
  58. 			cout<<i.F<<' '<<2*DR[v]+i.S<<"\n";
  59. 		}
  60. 		if(odw[i.F]==0) dfs2(i.F);
  61. 	}
  62. }
  63.  
  64. int main() {
  65. 	ios_base::sync_with_stdio(0);
  66. 	cin.tie(0);
  67. 	int n,m,u,v,w;
  68. 	cin>>n>>m;
  69. 	for(int i=1;i<n;i++){
  70. 		cin>>u>>v>>w;
  71. 		g[u].PB({v,w});
  72. 		g[v].PB({u,w});
  73. 	}
  74. 	for(int i=0;i<m;i++){
  75. 		cin>>u;
  76. 		PD[u]++;
  77. 	}
  78. 	dfs(1);
  79. 	for(int i=1;i<=n;i++) odw[i]=0;
  80. 	dfs2(1);
  81. 	for(int i=1;i<=n;i++) cout<<t[i]<<"\n";
  82. 	//cout<<2*DR[1]-MA1[1].F;
  83. }
Success #stdin #stdout 0.01s 34484KB
comments (?)
stdin
copy 
5 2
2 5 1
2 4 1
1 2 2
1 3 2
4 5
stdout
copy 
2 10
2 5
2 5
1 6
1 10
5
3
3
2
2
https://ideone.com/2VvDFx
language:
C++ (gcc 8.3)
created:
10 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!