近期心情不顺，坑了一堆没写的题解……（嗯我反演等回来再填坑吧（逃

好了还是说说这题吧，私以为鄙人的做法还是蛮妙的：

定义\(d(x)\)表示\(x\)到根上所有点的权值和，\(d_{max}(x)\)为\(x\)所在的子树中所有点的\(d(x)\)的最大值。对一个结点，他的所有儿子中\(d_{max}(x)\)最大的称为重儿子，其他作为轻儿子，然后做一遍树剖。然后将所有重链的权值和扔到一个数组里，降序排序，选前\(k\)大求和即可（不够的话全选）。

为什么？

显然，尽可能选叶子是划算的。然后，任意一条重链链顶的父亲所在的重链的权值和必定大于该重链，所以说不必担心某个重链选了而他的祖先却没有被记到答案里的情况。而若干这种重链的并，恰好对应了若干条到叶子路径的并。由于我们还是从大到小选的，所以答案是最优的。

代码：

/**************************************************************
    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;
}

• 相关文章
• 全局相关文章