P7232 [JSOI2014] 支线剧情 2 - 题解

chroneZ · 2023-08-02 16:35:41 · 题解

简单手玩一下，可以发现一定存在一种最优方案，能够一棵子树一棵子树地访问掉所有叶结点。

考虑树形 \text{dp}。记 f_u 表示当前所在位置为 u，且存档点也位于 u 时，走完 u 子树内所有叶结点的最小代价。

设 u 的一个子结点为 v，转移可以分为两种，一种是将存档点下放给 v，贡献为 f_v + w_{u, v} + dep_{u}，其中 dep_u 表示从根结点 1 到点 u 的距离。加 dep_u 是因为我们需要在访问完 v 内所有叶结点后，回到 u 结点以进行下一棵子树的决策。

另一种是不下放存档点，那么就需要从点 u 向 v 子树内的所有的叶结点走一遍。记 s_u 表示 u 子树内叶结点的数量，g_u 表示从点 u 出发到 u 子树内的所有叶结点的，共 s_u 条链的权值和。g 的转移显然，g_u = \sum \limits_{v \in son_u} g_v + w_{u, v}s_v。综上，这种转移的贡献为 g_v + w_{u, v}s_v。

当然，还可以任选一棵子树作为最后一个被处理的子树，使得处理完它后不需要再回到结点 u。这样转移的贡献为 f_v + w_{u, v}，且只能对至多一棵子树这样转移。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr int N = 1e6 + 10;
struct Graph {
    int head[N], total, v[N << 1], w[N << 1], suf[N << 1];
    Graph() {memset(head, -1, sizeof head);}
    inline void addedge(int x, int y, int t) {
        suf[total] = head[x]; head[x] = total;
        v[total] = y, w[total] = t; total++;
    }
} G;

i64 f[N], g[N], s[N], dep[N];
void dfs(int u, int fa) {
    int child = 0;
    for(int i = G.head[u]; ~i; i = G.suf[i]) {
        int v = G.v[i], w = G.w[i];
        if(v == fa) continue;
        dep[v] = dep[u] + w; dfs(v, u); 
        child++; s[u] += s[v]; g[u] += g[v] + w * s[v];
    }
    if(child == 0) s[u] = 1;
    i64 del = 0;
    for(int i = G.head[u]; ~i; i = G.suf[i]) {
        int v = G.v[i], w = G.w[i];
        if(v == fa) continue;
        i64 cur = min(f[v] + w + dep[u], g[v] + w * s[v]);
        i64 it = f[v] + w;
        del = max(del, cur - it);
        f[u] += cur;
    }
    f[u] -= del;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        int k; cin >> k;
        while(k--) {
            int v, w; cin >> v >> w;
            G.addedge(i, v, w), G.addedge(v, i, w);
        }
    }
    dfs(1, -1);
    cout << f[1] << "\n";
}