[BZOJ 3252]攻略
转载请注明出处:http://danihao123.is-programmer.com/
近期心情不顺,坑了一堆没写的题解……(嗯我反演等回来再填坑吧(逃
好了还是说说这题吧,私以为鄙人的做法还是蛮妙的:
定义d(x)表示x到根上所有点的权值和,dmax(x)为x所在的子树中所有点的d(x)的最大值。对一个结点,他的所有儿子中dmax(x)最大的称为重儿子,其他作为轻儿子,然后做一遍树剖。然后将所有重链的权值和扔到一个数组里,降序排序,选前k大求和即可(不够的话全选)。
为什么?
显然,尽可能选叶子是划算的。然后,任意一条重链链顶的父亲所在的重链的权值和必定大于该重链,所以说不必担心某个重链选了而他的祖先却没有被记到答案里的情况。而若干这种重链的并,恰好对应了若干条到叶子路径的并。由于我们还是从大到小选的,所以答案是最优的。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | /************************************************************** Problem: 3252 User: danihao123 Language: C++ Result: Accepted Time:1168 ms Memory:14600 kb ****************************************************************/ #include <cstdio> #include <algorithm> #include <utility> #include <cstring> #include <cctype> #include <cstdlib> #include <vector> #include <utility> typedef long long ll; const int maxn = 200005; const int maxm = maxn * 2; int first[maxn]; int next[maxm], to[maxm]; void add_edge( int u, int v) { static int cnt = 0; cnt ++; next[cnt] = first[u]; first[u] = cnt; to[cnt] = v; } ll A[maxn]; ll dsum[maxn], max_s[maxn]; int hson[maxn], hpre[maxn]; void dfs_1( int x, int fa) { dsum[x] = dsum[fa] + A[x]; max_s[x] = dsum[x]; hpre[x] = x; for ( int i = first[x]; i; i = next[i]) { int v = to[i]; if (v != fa) { dfs_1(v, x); if (max_s[x] < max_s[v]) { max_s[x] = max_s[v]; hson[x] = v; hpre[x] = hpre[v]; } } } } std::vector<ll> cho; void dfs_2( int x, int fa, ll s) { if (hson[x]) { dfs_2(hson[x], x, s + A[hson[x]]); } else { cho.push_back(s); return ; } for ( int i = first[x]; i; i = next[i]) { int v = to[i]; if (v != fa && v != hson[x]) { dfs_2(v, x, A[v]); } } } inline ll readint() { ll x = 0; char c; c = getchar (); while (! isdigit (c)) { c = getchar (); } while ( isdigit (c)) { x = x * 10LL + (ll(c - '0' )); c = getchar (); } return x; } bool cmp( const ll &a, const ll &b) { return a > b; } int main() { #ifdef DEBUG freopen ( "tour.in" , "r" , stdin); freopen ( "tour.out" , "w+" , stdout); #endif int n, k; n = readint(); k = readint(); for ( int i = 1; i <= n; i ++) { A[i] = readint(); } for ( int i = 1; i <= n - 1; i ++) { int u, v; u = readint(), v = readint(); add_edge(u, v); add_edge(v, u); } dfs_1(1, 0); dfs_2(1, 0, A[1]); std::sort(cho.begin(), cho.end(), cmp); ll ans = 0; for ( int i = 0; i < std::min(( int (cho.size())), k); i ++) { ans += cho[i]; } printf ( "%lld\n" , ans); // fclose(stdin); fclose(stdout); return 0; } |
3 年前
Tripura Board Model Paper 2023 Class 4 Pdf Download with Answers for Bengali Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. Tripura Board Question Paper Class 4 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.