fork download
  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];
  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.  
  33. int main() {
  34. ios_base::sync_with_stdio(0);
  35. cin.tie(0);
  36. int n,m,u,v,w;
  37. cin>>n>>m;
  38. for(int i=1;i<n;i++){
  39. cin>>u>>v>>w;
  40. g[u].PB({v,w});
  41. g[v].PB({u,w});
  42. }
  43. for(int i=0;i<m;i++){
  44. cin>>u;
  45. PD[u]++;
  46. }
  47. dfs(1);
  48. //for(int i=1;i<=n;i++) cout<<PD[i]<<" ";
  49. cout<<2*DR[1]-MA1[1].F;
  50. }
Success #stdin #stdout 0.01s 31168KB
stdin
5 2
2 5 1
2 4 1
1 2 2
1 3 2
4 5
stdout
5