SHARE
TWEET

ac

a guest Feb 16th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define sz(a) int((a).size())
  3. #define pb push_back
  4. #define all(c) (c).begin(),(c).end()
  5. #define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)
  6. #define present(c,x) ((c).find(x) != (c).end())
  7. #define cpresent(c,x) (find(all(c),x) != (c).end())
  8. #define LSOne(i) (i&(-i))
  9. #define rep(i,a,b) for(int(i)=(a);(i)<(b);i++)
  10. #define BUG(x) {cout<<#x<<" = "<<x<<endl;}
  11. #define left(x) (x<<1)
  12. #define right(x) ((x<<1) +1)
  13. #define middle(s,e)(s+(e-s)/2)
  14. #define size_tree(n) 2*(int)pow(2,ceil(log2(n)))
  15. #define CL(A,I) (memset(A,I,sizeof(A)))
  16. #define endl '\n'
  17. #define PHAS(_n) (pbits[(_n)>>5] & (1u << ((_n) & 0x1f)))
  18. #define PSET(_n) (pbits[(_n)>>5] |= (1u << ((_n) & 0x1f)))
  19. //unsigned int pbits[200000000/32+1];
  20.  
  21. static const int INF = 0x3f3f3f3f;
  22. static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
  23. static const long double epsilon = 1e-15;
  24. static const long double pi = acos((long double) -1);
  25. using namespace std;
  26. inline void init_io(){ios_base::sync_with_stdio(false);cin.tie(NULL);}
  27.  
  28. typedef vector<int> vi;
  29. typedef vector<vi> vvi;
  30. typedef pair<int,int> ii;
  31. typedef long long ll;
  32.  
  33. const int N = 100001;
  34.  
  35. vector<int> tree[N];
  36. int w[N], par[N], child[N];
  37.  
  38. struct data{
  39.   int weight;
  40.   int idx;
  41.   data():weight(0), idx(0){};
  42.   data(int w, int i) : weight(w), idx(i){};
  43.   bool operator < (data other) const {
  44.     return weight > other.weight;
  45.   }
  46. };
  47.  
  48. priority_queue<data> pq;
  49.  
  50. void dfs(int u,int p)
  51. {
  52.     rep(i,0,tree[u].size())
  53.     {
  54.         int v = tree[u][i];
  55.         if(v==p) continue;
  56.         par[v] = u ;
  57.         dfs(v,u);
  58.     }
  59.     if(tree[u].size()==1)
  60.         pq.push(data(w[u],u));
  61. }
  62.  
  63. int main()
  64. {
  65.         int n,k,u,v;
  66.         cin>>n>>k;
  67.         long res = 0;
  68.         rep(i,0,n)
  69.         {
  70.             cin>>w[i];
  71.             res +=w[i];
  72.         }
  73.         rep(i,0,n-1)
  74.         {
  75.             cin>>u>>v;
  76.             u--;v--;
  77.             tree[u].pb(v);
  78.             tree[v].pb(u);
  79.         }
  80.         rep(i,0,n)
  81.             child[i] = tree[i].size()-1;
  82.         dfs(0,-1);
  83.         rep(i,0,k)
  84.         {
  85.             data d = pq.top();
  86.             pq.pop();
  87.             res-= d.weight;
  88.             child[par[d.idx]]--;
  89.             if(!child[par[d.idx]])
  90.                 pq.push(data(w[par[d.idx]],par[d.idx]));
  91.         }
  92.         cout<<res<<endl;
  93.     return 0;
  94. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top