小欧吃苹果

[题目链接](https://www.nowcoder.com/practice/1e681787c63045cdbfc26b9b09002aeb)

思路

一棵 个结点的树，结点 上的人当前有 个苹果，想吃恰好 个。每次操作可以沿一条边传递 1 个苹果，求最小总传递次数。

关键观察：边上的流量

对于树上的任意一条边 ，删掉这条边后树被分成两个连通分量。设其中一个分量的结点集合为 ，则 中所有人的"盈余"之和为：

$$

如果 ，说明 中有多余的苹果需要向外运出；如果 ，说明需要从外面运入。无论哪种情况，经过边 的苹果传递次数恰好是 。

因此，最小总传递次数等于所有边上流量之和：

$$

实现方法

以结点 1 为根，对树做一次 BFS，然后按逆 BFS 序（从叶子到根）累加每个子树的盈余。对于每个非根结点 ， 就是边 上的流量，将它累加到答案中，然后把 加到 上。

样例演示

树的结构：1-2, 1-3, 2-4，苹果分布 。

各结点盈余：，，，。

  • 结点 4：，累加到父结点 2：
  • 结点 3：，累加到父结点 1：
  • 结点 2：，累加到父结点 1：

答案 ，与预期一致。

复杂度

  • 时间复杂度：，一次 BFS 加一次逆序遍历。
  • 空间复杂度：，存储树和辅助数组。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<long long> sub(n + 1);
    for (int i = 1; i <= n; i++) sub[i] = a[i] - i;
    vector<int> parent(n + 1, 0);
    vector<bool> vis(n + 1, false);
    vector<int> order;
    queue<int> q;
    q.push(1); vis[1] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    long long ans = 0;
    for (int i = n - 1; i >= 1; i--) {
        int u = order[i];
        ans += abs(sub[u]);
        sub[parent[u]] += sub[u];
    }
    printf("%lld\n", ans);
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        long[] a = new long[n + 1];
        for (int i = 1; i <= n; i++) a[i] = Long.parseLong(st.nextToken());
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine().trim());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        long[] sub = new long[n + 1];
        for (int i = 1; i <= n; i++) sub[i] = a[i] - i;
        int[] parent = new int[n + 1];
        boolean[] vis = new boolean[n + 1];
        int[] order = new int[n];
        int head = 0, tail = 0;
        order[tail++] = 1;
        vis[1] = true;
        while (head < tail) {
            int u = order[head++];
            for (int v : adj.get(u)) {
                if (!vis[v]) {
                    vis[v] = true;
                    parent[v] = u;
                    order[tail++] = v;
                }
            }
        }
        long ans = 0;
        for (int i = n - 1; i >= 1; i--) {
            int u = order[i];
            ans += Math.abs(sub[u]);
            sub[parent[u]] += sub[u];
        }
        System.out.println(ans);
    }
}