CF1987E Wonderful Tree! 题解

Preface

提供一种比较小众但是不太动脑子的做法。

Problem

给你一棵 $n$ 个点的有根树 $T$，点有点权 $a$，你可以通过一次操作增加一个点的点权，要求对于所有的非叶子节点 $u$：

其中 $son_u$ 代表 $u$ 在有根树中的儿子集合。
问使树合法的最小操作次数。
$2 \le n \le 5000,\ 0 \le a_i \le 10^9$。

Solution

我们把式子变动一下，设：

则我们要让所有非叶子的 $b$ 都小于等于 $0$。
考虑一次对 $u$ 的操作会对 $b$ 产生什么影响。
显然会让 $b_u$ 加一，但是会让 $b_{fa}$（$fa$ 为 $u$ 的父亲）减一。
这也可以理解为把一个地方的贡献挪到了父亲，花费为 $1$。

(a,b,c,d) 分别为一条边的起始点，终止点，流量限制，单位流量费用，S 为源点，T 为汇点。

通过上述观察，我们可以建立费用流模型：

• 对于每个非根节点 $u$：连边 $(u,fa,inf,1)$。
• 对于每个非叶子节点 $u$：
  • 若 $b_u < 0$，连边 $(S, u, -b_u, 0)$。
  • 若 $b_u > 0$，连边 $(u, T, b_u, 0)$。
• 对于每个叶子节点 $u$：连边 $(S, u, inf, 0)$。

直接跑费用流即为答案，分析可知单次增广复杂度为 $O(n)$，总增广次数为 $O(n)$，总体复杂度为 $O(n^2)$。

Code

#include <bits/stdc++.h>
#define mp make_pair
#define fir first
#define sec second
#define int long long
using namespace std;

const int N = 5010;
int T, n, a[N], p[N], b[N], dep[N];
vector<int> edge[N];
int ans = 0;

namespace MCMF {
    const int N = 1e6 + 10;
    int n, s, t, head[N], to[N], nxt[N], f[N], c[N], cnt = -1;
    int maxflow, mincost;

    void add(int u, int v, int fl, int w) {
        ++cnt;
        nxt[cnt] = head[u];
        head[u] = cnt;
        to[cnt] = v;
        f[cnt] = fl;
        c[cnt] = w;
        ++cnt;
        nxt[cnt] = head[v];
        head[v] = cnt;
        to[cnt] = u;
        f[cnt] = 0;
        c[cnt] = -w;
    }

    int dis[N], vis[N], pre[N][2];

    void SPFA() {
        queue<int> Q;
        for (int i = 0; i <= n; i++)
            dis[i] = 1e9, vis[i] = 0, pre[i][0] = pre[i][1] = 0;
        Q.push(s);
        vis[s] = 1;
        dis[s] = 0;
        while (Q.size()) {
            int u = Q.front();
            Q.pop();
            vis[u] = 0;
            for (int i = head[u]; ~i; i = nxt[i]) {
                int v = to[i], w = c[i];
                if (!f[i]) continue;
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    pre[v][0] = u;
                    pre[v][1] = i;
                    if (!vis[v]) {
                        Q.push(v);
                        vis[v] = 1;
                    }
                }
            }
        }
    }

    void solve() {
        mincost = 0;
        maxflow = 0;
        while (true) {
            SPFA();
            if (dis[t] == 1e9) return;
            int minf = 1e18, sumc = 0, now = t;
            vector<int> path;
            while (now != s) {
                path.push_back(pre[now][1]);
                minf = min(minf, f[pre[now][1]]);
                sumc += c[pre[now][1]];
                now = pre[now][0];
            }
            for (auto it : path) {
                f[it] -= minf;
                f[it ^ 1] += minf;
            }
            maxflow += minf;
            mincost += minf * sumc;
        }
    }
}  // namespace MCMF

void solve() {
    cin >> n;
    ans = 0;
    MCMF::cnt = -1;
    for (int i = 0; i <= n + 1; i++) MCMF::head[i] = -1;
    MCMF::s = 0;
    MCMF::t = n + 1;

    for (int i = 1; i <= n; i++)
        cin >> a[i], edge[i].clear(), b[i] = a[i];

    for (int i = 2; i <= n; i++)
        cin >> p[i], edge[p[i]].push_back(i);

    for (int i = 1; i <= n; i++) {
        if (edge[i].size() == 0) continue;
        b[i] = a[i];
        for (auto j : edge[i]) b[i] -= a[j];
    }

    MCMF::n = n + 1;

    for (int i = 2; i <= n; i++)
        MCMF::add(i, p[i], 1e18, 1);

    for (int i = 1; i <= n; i++) {
        if (edge[i].size() == 0) {
            MCMF::add(0, i, 1e18, 0);
            continue;
        }
        if (b[i] < 0) {
            MCMF::add(0, i, -b[i], 0);
        } else if (b[i] > 0) {
            MCMF::add(i, n + 1, b[i], 0);
        }
    }

    MCMF::solve();
    cout << MCMF::mincost << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T--) solve();
    return 0;
}