CF1120D 题解

题面链接

题意

有一棵有根树，根节点编号为$1$。每个点都有一个权值$w_i$。
现在给每个叶子节点一个数$c_i$，你可以花费$w_i$购买下$i$这个节点，使其子树内的所有叶子节点的值加上一个正数。对于任意的$c_i$，求出所有花费最少的能够使所有叶子节点上的数字相同的方案的并集。

分析

首先，很自然的可以想到叶子节点可以按照访问顺序排列，这样每棵子树都是一个区间，子树内的叶子权值都加上一个数就是区间加法。
其次，题目要求我们使得所有的叶子节点上的数相同。我们想，对于一个序列，如果他的每一项都相同，那么他的差分序列就是一段$0$。那么，在区间$[l,r]$上的区间修改，就可以转化为在差分序列上的$l$点和$r+1$两个点的单点修改。
进一步推导，我们可以发现，对于$l$和$r+1$两个点的单点修改，最少可以把一个点上的数变为$0$。而想要把$n+1$个数中的$n$个^[1]都变成$0$，那么就要选择$n$个区间。很显而易见的，这就可以转化成一个最小生成树问题：一个节点$x$，对应的边就是$(l_x,r_x+1,w_x)$。这样，问题就解决了。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-')
      f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return x * f;
}
const int N = 2E5 + 10;
int n;
int w[N];
// graph
int head[N], to[N << 1], nxt[N << 1], ecnt;
void adde(int a, int b) {
  ecnt++;
  nxt[ecnt] = head[a];
  head[a] = ecnt;
  to[ecnt] = b;
}
// DSU
int f[N];
int findf(int x) { return f[x] == 0 ? x : f[x] = findf(f[x]); }
// Kruskal;
int leaves[N], //这个节点子树中的叶子节点个数
    id;        // 叶子节点个数
bool selected[N];
struct edge {
  int from, to, w, v;
} es[N << 1];
int necnt;
void inse(int a, int b, int w, int v) {
  necnt++;
  es[necnt] = {a, b, w, v};
}
void kruskal() {
  sort(es + 1, es + 1 + necnt,
       [](const edge &a, const edge &b) { return a.w < b.w; });
  int l = 1;
  int k = 0;
  int mst = 0;
  while (l <= n) {
    int r;
    // 统计重复的边
    for (r = l; r <= n; r++) {
      if (es[r].w != es[r + 1].w)
        break;
    }
    // 因为要求并集，所以都要选上
    for (int i = l; i <= r; i++) {
      if (findf(es[i].from) != findf(es[i].to)) {
        selected[es[i].v] = 1;
        k++;
      }
    }
    // 统计一次边的权值
    for (int i = l; i <= r; i++) {
      int fu = findf(es[i].from);
      int fv = findf(es[i].to);
      if (fu == fv)
        continue;
      mst += es[i].w;
      f[fu] = fv;
    }
    l = r + 1;
  }
  // 输出
  cout << mst << ' ' << k << endl;
  for (int i = 1; i <= n; i++) {
    if (selected[i])
      cout << i << ' ';
  }
  cout << endl;
}
void dfs1(int x, int fa) {
  bool vis = 0; // 有儿子，不是叶子节点
  for (int i = head[x]; i; i = nxt[i]) {
    int v = to[i];
    if (v != fa) {
      dfs1(v, x);
      vis = 1;
      leaves[x] += leaves[v];
    }
  }
  if (!vis) { // 是叶子节点
    id++;
    leaves[x] = 1;
  }
}
void dfs2(int x, int fa, int l) {
  // clog << l << "==>" << l + leaves[x] << ", w=" << w[x] << ", node " << x
  // << endl;

  // 统计子树
  inse(l, l + leaves[x], w[x], x);
  for (int i = head[x]; i; i = nxt[i]) {
    int v = to[i];
    if (v != fa) {
      dfs2(v, x, l);
      l += leaves[v];
    }
  }
}
signed main() {
  n = read();
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
  }
  for (int i = 1; i < n; i++) {
    int a = read(), b = read();
    adde(a, b);
    adde(b, a);
  }
  dfs1(1, 0);
  dfs2(1, 0, 1);
  kruskal();
  return 0;
}

C++

1. 这是因为差分序列的第一项可以不为$0$，所以只需要选。 ↩