Orz hzwer
只要用堆就可以了，跪烂了。。。
话说那个什么ext的库真的能用嘛= =，反正我用了烂删除
结果Rank.3←_←
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 ", ans); 95 return 0; 96 }
（p.s. 开了二逼读入以后就变成Rank.1了2333）