• API
• FAQ
• Tools
• Archive
daily pastebin goal
34%
SHARE
TWEET

# ac

a guest Feb 16th, 2019 70 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.

Top