Advertisement
Josif_tepe

Untitled

Dec 2nd, 2023
891
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn = 1e5 + 10;
  5. const ll INF = 1e18;
  6. int n, k;
  7. vector<pair<int, int> > graph[maxn];
  8. bool pay_toll[maxn];
  9.  
  10. pair<ll, ll> dfs(int node, int parent) {
  11.     ll res = 0, sum = 0, max_edge = 0;
  12.     for(int i = 0; i < (int) graph[node].size(); i++) {
  13.         int neighbour = graph[node][i].first;
  14.         if(neighbour != parent) {
  15.             ll weight = graph[node][i].second;
  16.             pair<ll, ll> p = dfs(neighbour, node);
  17.             res += p.first;
  18.             sum += min(weight, p.second);
  19.             max_edge = max(max_edge, min(weight, p.second));
  20.         }
  21.     }
  22.     if(pay_toll[node]) {
  23.         res += sum;
  24.         max_edge = INF;
  25.     }
  26.     else {
  27.         res += sum - max_edge;
  28.     }
  29.     return make_pair(res, max_edge);
  30. }
  31. int main()
  32. {
  33.     ios_base::sync_with_stdio(false);
  34.     cin >> n >> k;
  35.    
  36.     for(int i = 1; i < n; i++) {
  37.         int a, b, c;
  38.         cin >> a >> b >> c;
  39.         graph[a].push_back(make_pair(b, c));
  40.         graph[b].push_back(make_pair(a, c));
  41.     }
  42.     for(int i = 0; i < maxn; i++) {
  43.         pay_toll[i] = false;
  44.     }
  45.    
  46.     for(int i = 0; i < k; i++) {
  47.         int x;
  48.         cin >> x;
  49.         pay_toll[x] = true;
  50.     }
  51.     cout << dfs(0, -1).first << endl;
  52.     return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement