fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp> // Common file
  3. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  4. #define int long long
  5. #define mod 1000000007
  6. #define maxN 100005
  7. #define pb push_back
  8. #define mp make_pair
  9. #define pii pair<int,int>
  10. #define pip pair<int,pii>
  11. #define vi vector<int>
  12. #define vpi vector<pii >
  13. #define endl "\n"
  14. #define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  15. #define FOR(a,b,c) for(int(a) = b;a<=c;a++)
  16. #define repr(a,b,c) for(int(a) = b;a>=c;a--)
  17. #define rep(i,n) for(int(i) = 0;i<n;i++)
  18. #define fir first
  19. #define sec second
  20. #define beg begin()
  21. #define e end()
  22. #define len length()
  23. using namespace std;
  24. using namespace __gnu_pbds;
  25. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  26. typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
  27. bool comp(pii a,pii b){
  28.   return a.sec < b.sec;
  29. }
  30. int val[maxN];
  31. int q;
  32. vpi g[maxN];
  33. pii mark[maxN];
  34. int tim = 0;
  35. void dfs(int x,int par){
  36.   rep(i,g[x].size()){
  37.     int y = g[x][i].fir;
  38.     if(y == par)continue;
  39.     tim++;
  40.     int w = g[x][i].sec;
  41.     int ind = upper_bound(val,val+q,w) - val;
  42.     mark[ind] = mp(y,tim);
  43.     dfs(y,x);
  44.   }
  45. }
  46. int32_t main()
  47. {
  48.    fastIO;
  49.    int t;
  50.    cin>>t;
  51.    while(t--){
  52.      int n;
  53.      tim = 0;
  54.      cin>>n>>q;
  55.      int x,y,w;
  56.      rep(i,n-1){
  57.        cin>>x>>y>>w;
  58.        g[x].pb(mp(y,w));
  59.        g[y].pb(mp(x,w));
  60.      }
  61.      FOR(i,1,n){
  62.        sort(g[i].beg,g[i].e,comp);
  63.      }
  64.      rep(i,q){
  65.        cin>>val[i];
  66.        mark[i]=mp(1,0);
  67.      }
  68.      sort(val,val+q);
  69.      dfs(1,1);
  70.      int ans = 0;
  71.      int last = mark[0].fir;
  72.      tim = mark[0].sec;
  73.      rep(i,q){
  74.        //cout<<mark[i]<<' ';
  75.        if(mark[i].sec > tim){
  76.          last = mark[i].fir;
  77.          tim = mark[i].sec;
  78.        }
  79.        ans+=last;
  80.      }
  81.      cout<<ans<<endl;
  82.      FOR(i,1,n)g[i].clear();
  83.    }
  84.  
  85.    return 0;
  86. }
  87.  
Success #stdin #stdout 0s 6024KB
comments (?)
stdin
copy 
1
5 7
1 2 3
1 3 4
3 4 9
3 5 7
1 3 4 9 8 7 10
stdout
copy 
21
https://ideone.com/dC46tT
language:
C++14 (gcc 8.3)
created:
5 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!