1 /************************************************************** 2     Problem: 3252 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:964 ms 7     Memory:14036 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <algorithm>12 #include <queue>13  14 using namespace std;15 typedef long long ll;16 const int N = 200005;17  18 struct edges {19     int next, to;20     edges() {}21     edges(int _n, int _t) : next(_n), to(_t) {}22 } e[N];23  24 struct data {25     ll first;26     int w;27     data() {}28     data(ll _f, int _w) : first(_f), w(_w) {}29      30     inline bool operator < (const data &b) const {31         return first < b.first;32     }33 };34  35 int n, k;36 int first[N], tot;37 int v[N];38 bool vis[N];39 ll mx[N], ans;40 priority_queue <data> h;41  42 inline int read() {43     int x = 0, sgn = 1;44     char ch = getchar();45     while (ch < ‘0‘ || ‘9‘ < ch) {46         if (ch == ‘-‘) sgn = -1;47         ch = getchar();48     }49     while (‘0‘ <= ch && ch <= ‘9‘) {50         x = x * 10 + ch - ‘0‘;51         ch = getchar();52     }53     return sgn * x;54 }55  56 inline void add_edge(int x, int y) {57     e[++tot] = edges(first[x], y);58     first[x] = tot;59 }60  61 void dfs(int p) {62     int x, y;63     for (x = first[p]; x; x = e[x].next)64         dfs(y = e[x].to), mx[p] = max(mx[p], mx[y]);65     mx[p] += v[p];66     h.push(data(mx[p], p));67 }68  69 void del(int p) {70     int x, y;71     vis[p] = 1;72     for (x = first[p]; x; x = e[x].next) 73         if (mx[y = e[x].to] == mx[p] - v[p]) {74             del(y);75             break;76         }77 }78  79 int main() {80     int i, p, x, y;81     n = read(), k = read();82     for (i = 1; i <= n; ++i) v[i] = read();83     for (i = 1; i < n; ++i) {84         x = read(), y = read();85         add_edge(x, y);86     }87     dfs(1);88     for (; k && !h.empty(); --k) {89         while (vis[h.top().w] && !h.empty()) h.pop();90         if (h.empty()) break;91         ans += mx[p = h.top().w];92         del(p);93     }94     printf("%lld\n", ans);95     return 0;96 }