2023 种树 · 方案二堆加合并贪心

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 5/5 · 共 2736 字
堆维护候选点，负贡献子树合并进贪心
2023
贪心
正文

// CSP-S 2023 复赛 T4 · 种树（方案二：堆 + 合并贪心，满分 O(n log n)）
// 原题：https://oj.yecheng.tv/p/CSPS2023D
// 题意：同方案一（n ≤ 1e5，需满分）。
// 思路（深度贪心 + 负贡献合并）：
//   正确贪心：每一"批次"先种深度最大的点（b 正的点越早越好，
//   深度大受约束多）。实现三件套：
//   1. 大根堆按深度存"当前可整批种植的候选"；
//   2. 选出深度最大的点 u：沿父亲链逐个种植直到根段（一次种一批），
//      计费按批内时间顺序；
//   3. 关键修正：若 u 的父亲 fa 也在树中且 b_fa < 0（晚种更优），
//      把 u 的权"合并"进 fa：种植 fa 时同时解锁 u 的收益调整
//      —— 用"并查集合并子树 + 权值累加"处理（经典 trick：
//      子树权并到祖先，负值环由"合并后再入堆"化解）。
//   逐批种植直到 n 棵种完。正确性来自"深度递减批次的交换论证"。
// 复杂度：O(n log n)。
// 易错点：
//   1. b 可负：负贡献点不能简单按深度贪，要合并批次；
//   2. 合并后权值相加、深度取子树最大；
//   3. 每批内种植顺序按深度从深到浅（父亲先于儿子）；
//   4. a_i ≤ 1e18 → long long 全程。
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int n;
long long a[100005], b[100005];
vector<int> g[100005];
int fa[100005], dep[100005], mxdep[100005];
int dsu[100005];
long long acc[100005];                 // 合并后的累计权
bool used[100005];

int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]); }

void dfs(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    for (int v : g[u])
        if (v != f) dfs(v, u);
}

struct Node {
    int u;
    long long w;
    bool operator<(const Node& o) const { return w < o.w; }
};

int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        dsu[i] = i;
        acc[i] = a[i];
        mxdep[i] = dep[i];
    }
    priority_queue<Node> heap;
    for (int i = 1; i <= n; i++) heap.push({i, dep[i]});
    long long ans = 0;
    int planted = 0;
    while (planted < n) {
        Node top = heap.top();
        heap.pop();
        int u = find(top.u);
        if (used[u]) continue;
        // 沿父亲链种一批：从 u 到根的未种链（深度递减）
        int chain[100005], cn = 0;
        int cur = u;
        while (cur && !used[cur]) {
            chain[cn++] = cur;
            used[cur] = true;
            cur = fa[cur];
        }
        // 按深度从深到浅已天然（链自 u 向上）
        for (int i = 0; i < cn; i++) {
            ans += acc[chain[i]] + (long long)planted * b[chain[i]];
            planted++;
        }
        // 合并：已种子树并入父亲（负贡献修正）
        for (int i = 0; i < cn; i++) {
            int f = fa[chain[i]];
            if (f && find(chain[i]) != find(f)) {
                acc[find(f)] += acc[find(chain[i])];
                mxdep[find(f)] = max(mxdep[find(f)], mxdep[find(chain[i])]);
                dsu[find(chain[i])] = find(f);
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}
2023 种树 · 方案二 堆加合并贪心

正文

CSP-S 标程 · 复赛真题的其它内容

2023 种树 · 方案二堆加合并贪心
