树形 DFS 与"三数之积"剪枝：以 codeforces-go 仓库详解 LeetCode 2973 在树节点中放置硬币

本文以 codeforces-go 仓库中双周赛 120 第 4 题的完整题解（leetcode/biweekly/120/d/README.md）为核心，讲解一道树形结构 + 乘积最值的综合题：如何在自底向上的 DFS 中只保留每棵子树最关键的 5 个值（最小 2 个、最大 3 个），从而用 O(n log n) 时间求出每个节点的答案。读完本文，你将掌握"三数之积"问题的完整分类讨论框架，以及"只保留极值、丢弃中间值"这一可迁移到多类树上聚合问题的剪枝技巧，并看到该解法在仓库中的 Go 实现与自动化测试全貌。

问题回顾：在树节点中放置硬币

题目给定一棵由 edges 描述的树（n 个节点，edges[i] = [x, y] 表示节点间的一条无向边）以及每个节点的花费数组 cost。要求对每一个节点 x，在其子树（以节点 0 为根时）的所有节点花费中，任选三个不同节点的 cost 值求乘积，返回三数之积的最大值；若该最大值为负数，则返回 0；若子树中节点数不足 3 个，则返回 1。

该题即双周赛 120 的第 4 题（Find Number of Coins to Place in Tree Nodes），仓库中的题目编号注释见 d_test.go。题目本身是"树的每个子树求三数之积最值"这一朴素问题，难点在于如何避免每个节点都做一次 O(size) 级全量排序，从而把总复杂度控制在可接受的范围内。

核心观察：三数之积只需要 5 个数

文档首先剥离树形结构，把问题抽象为一个独立的小问题：给你一个长度 ≥ 3 的数组，返回三数之积的最大值；如果最大值是负数，返回 0。

关键结论只有两条：

• 如果只考虑正数，显然最大的三个数的乘积是最大的；
• 如果把负数也考虑进来，那么"最小的两个负数 × 最大的正数"也可能成为最大值（因为两个负数相乘得正，且负数绝对值越大、相乘结果越大，所以取最小的两个负数）。

这两种情况的结果再与 0 取最大值，即为返回值。写成公式即：

ans = max(最大三个数之积, 最小两个数之积 × 最大一个数, 0)

由此得到最重要的推论：只需要知道 5 个数——最小的 2 个值和最大的 3 个值——就能算出三数之积的最大值，其余数字全部可以舍弃。 这一观察是整道题复杂度优化的根基：每棵子树向上返回时不需要带回全部节点花费，只需返回这 5 个关键值。

算法设计：自底向上的树形 DFS

有了 5 个关键值的前提，算法就非常清晰了：

1. 建图：根据 edges 建立无向邻接表 g，由于题目输入的是无向边，每条边需要双向添加（d.go 中 g[x] = append(g[x], y) 与 g[y] = append(g[y], x) 各执行一次）。
2. DFS 聚合：定义 dfs(x, fa) 返回节点 x 子树中"最小的 2 个值与最大的 3 个值"。实现时先将当前节点自身的 cost[x] 加入集合，再递归遍历所有儿子 y != fa（用父节点参数避免走回头路），把每个儿子返回的关键值 extend 进当前集合。
3. 计算当前节点答案：将聚合得到的数组 a 排序后，按三数之积公式计算：
   • 若 len(a) < 3，说明子树节点不足，答案为 1；
   • 否则 ans[x] = max(a[-3]*a[-2]*a[-1], a[0]*a[1]*a[-1], 0)，即"最大三个"与"最小两个 × 最大一个"两者取大后与 0 取大。
4. 向上裁剪：若 len(a) > 5，只保留 a[:2] + a[-3:]（最小的 2 个 + 最大的 3 个）并返回，中间值全部丢弃，保证每次向上传递的数组规模恒 ≤ 5。

最终从根 dfs(0, -1) 出发，一次遍历填满所有节点的 ans。注意这里数组排序后 a[-3]*a[-2]*a[-1] 与 a[0]*a[1]*a[-1] 恰好覆盖了正负数全部情况：前者覆盖"全正 / 偶数个负数"的最大组合，后者覆盖"两个绝对值最大的负数"参与的组合。

多语言实现：完整代码对照

文档同时给出了 Python3、Java、C++ 与 Go 四种实现，逻辑完全一致，下面完整列出。

Python3

class Solution:
    def placedCoins(self, edges: List[List[int]], cost: List[int]) -> List[int]:
        n = len(cost)
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        ans = [1] * n
        def dfs(x: int, fa: int) -> List[int]:
            a = [cost[x]]
            for y in g[x]:
                if y != fa:
                    a.extend(dfs(y, x))
            a.sort()
            m = len(a)
            if m >= 3:
                ans[x] = max(a[-3] * a[-2] * a[-1], a[0] * a[1] * a[-1], 0)
            if m > 5:
                a = a[:2] + a[-3:]
            return a
        dfs(0, -1)
        return ans

Java

class Solution {
    public long[] placedCoins(int[][] edges, int[] cost) {
        int n = cost.length;
        List<Integer>[] g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x);
        }

        long[] ans = new long[n];
        dfs(0, -1, cost, g, ans);
        return ans;
    }

    private List<Integer> dfs(int x, int fa, int[] cost, List<Integer>[] g, long[] ans) {
        List<Integer> a = new ArrayList<>();
        a.add(cost[x]);
        for (int y : g[x]) {
            if (y != fa) {
                a.addAll(dfs(y, x, cost, g, ans));
            }
        }
        Collections.sort(a);
        int m = a.size();
        if (m < 3) {
            ans[x] = 1;
        } else {
            ans[x] = Math.max((long) a.get(m - 3) * a.get(m - 2) * a.get(m - 1),
                    Math.max((long) a.get(0) * a.get(1) * a.get(m - 1), 0));
        }
        if (m > 5) {
            a = List.of(a.get(0), a.get(1), a.get(m - 3), a.get(m - 2), a.get(m - 1));
        }
        return a;
    }
}

注意 Java 版需要把乘积显式转为 long，避免三个 int 相乘溢出——这一点在 Go 版中由 int64 返回值天然兜底，其余语言同理需要考虑乘积范围。

C++

class Solution {
public:
    vector<long long> placedCoins(vector<vector<int>>& edges, vector<int>& cost) {
        int n = cost.size();
        vector<vector<int>> g(n);
        for (auto& e: edges) {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }

        vector<long long> ans(n, 1);
        auto dfs = & -> vector<int> {
            vector<int> a = {cost[x]};
            for (int y: g[x]) {
                if (y != fa) {
                    auto res = dfs(dfs, y, x);
                    a.insert(a.end(), res.begin(), res.end());
                }
            }
            ranges::sort(a);
            int m = a.size();
            if (m >= 3) {
                ans[x] = max(max((long long) a[m - 3] * a[m - 2] * a[m - 1], (long long) a[0] * a[1] * a[m - 1]), 0LL);
            }
            if (m > 5) {
                a = {a[0], a[1], a[m - 3], a[m - 2], a[m - 1]};
            }
            return a;
        };
        dfs(dfs, 0, -1);
        return ans;
    }
};

Go（对应仓库源码 d.go）

func placedCoins(edges [][]int, cost []int) []int64 {
	n := len(cost)
	g := make([][]int, n)
	for _, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], y)
		g[y] = append(g[y], x)
	}

	ans := make([]int64, n)
	var dfs func(int, int) []int
	dfs = func(x, fa int) []int {
		a := []int{cost[x]}
		for _, y := range g[x] {
			if y != fa {
				a = append(a, dfs(y, x)...)
			}
		}

		slices.Sort(a)
		m := len(a)
		if m < 3 {
			ans[x] = 1
		} else {
			ans[x] = int64(max(a[m-3]*a[m-2]*a[m-1], a[0]*a[1]*a[m-1], 0))
		}
		if m > 5 {
			a = append(a[:2], a[m-3:]...)
		}
		return a
	}
	dfs(0, -1)
	return ans
}

该实现与仓库中的 d.go 逐行一致：使用 slices.Sort（Go 1.21+ 标准库排序）、max 三参数内置函数，且通过 a = append(a[:2], a[m-3:]...) 一步完成"保留最小 2 个 + 最大 3 个"的原地裁剪。四个版本的裁剪逻辑完全同构：a[:2] + a[-3:]（Python）、List.of(a[0], a[1], a[m-3], a[m-2], a[m-1])（Java）、初始化列表（C++）、append(a[:2], a[m-3:]...)（Go）。

复杂度分析

• 时间复杂度：O(n log n)，其中 n 为节点个数。每次递归都需要对聚合数组排序；由于裁剪后每个节点向上传递的数组规模 ≤ 5，每个节点处理的元素数是常数级，排序开销之和为 O(n log n)。文档明确指出：如果手动维护最小的两个数和最大的三个数，可以做到 O(n)——即用 5 个变量做"插入式"极值维护，免去排序。
• 空间复杂度：O(n)，主要来自邻接表 g、答案数组 ans 以及递归过程中每个节点持有的临时数组（每个节点裁剪后的数组 ≤ 5 个元素）。

需要说明的是：即使在"每个节点都只处理常数个元素"的情况下仍然出现 O(n log n)，是因为实现选择了"先合并再排序"的通用写法，方便读者理解；追求极致时可改为在合并过程中用 5 个变量在线维护最值，排序复杂度即被消除。

仓库实测：测试用例与自动化测试基建

仓库对该题配有完整的可运行工程：解法文件 d.go、测试用例数据 d.txt 以及测试驱动 d_test.go。用 go test ./leetcode/biweekly/120/d 即可在本地验证实现。

d.txt 采用"输入行 + 输出行"交替的格式，每 3 行一组（2 个入参 + 1 个出参），共 3 组用例。逐个推演可以加深对算法的理解：

用例 1：星型树，根 0 直接连 5 个叶子，cost = [1,2,3,4,5,6]。

• 根节点 0 的子树包含全部 6 个值，排序后最大三个为 4×5×6 = 120，最小两个为 1×2，故 ans[0] = 120；
• 其余叶子子树各只有 1 个节点（不足 3 个），答案均为 1。
• 期望输出：[120,1,1,1,1,1]，与 d.txt 第 3 行完全一致。

用例 2：三层树，cost = [1,4,2,3,5,7,8,-4,2]。

• 节点 0 子树含全部值：最大三个 5×7×8 = 280，最小两个 -4×1 乘最大 8 得 -32，取大并与 0 比较后 ans[0] = 280；
• 节点 1 子树（含 1、3、4、5 号节点）值为 [4,3,5,7]，最大三个 4×5×7 = 140，故 ans[1] = 140；
• 节点 2 子树（含 2、6、7、8 号节点）值为 [2,8,-4,2]，最大三个 2×2×8 = 32，故 ans[2] = 32；
• 叶子节点答案均为 1。
• 期望输出：[280,140,32,1,1,1,1,1,1]，与 d.txt 第 6 行一致。这一用例同时验证了"存在负数时取最小两个负数 × 最大正数"的边界分支没有被错误启用。

用例 3：链状小树，cost = [1,2,-2]。

• 根 0 子树值为 [1,2,-2]：1×2×(-2) = -4，(-2)×1×2 = -4，两个候选均为负，与 0 取大后 ans[0] = 0；
• 两个叶子答案均为 1。
• 期望输出：[0,1,1]，与 d.txt 第 9 行一致。该用例专门验证了"三数之积最大值为负数时返回 0"这一题目约束。

测试驱动部分，d_test.go 调用仓库测试基建中的 testutil.RunLeetCodeFuncWithFile(t, placedCoins, "d.txt", 0)。该函数（定义于 leetcode/testutil/leetcode.go）会按函数签名通过反射推断入参与出参个数（fNumIn + fNumOut），把 d.txt 按每组固定行数切分成测试用例，再逐组调用解法函数比对输出；targetCaseNum = 0 表示运行文件中全部用例。这套机制是仓库中所有 LeetCode 题目共用的通用测试管线，保证了题解在大量样例上的正确性。

总结与思维延伸

本题的价值不止于 AC 本身，更在于两个可复用的通用技巧：

1. 极值裁剪思想："三数之积"这类只依赖有序序列两端极值的聚合问题，只需要向上传递 O(1) 个关键值（最小 2 个 + 最大 3 个），中间值完全不影响父节点的决策。这一技巧可推广到任何"取若干端值"的树上聚合场景（如最大值、最小值、次值、前缀后缀极值组合等）。
2. 父子传递的 DFS 模板：dfs(x, fa) 配合 y != fa 防回边的写法，是无向树自底向上遍历的标准姿势，配合本题的"裁剪返回值"，即构成"树上聚合 + 信息压缩"的完整解题模板。

若想继续深入这类树上 DP 与极值维护的题目，可参照本仓库 copypasta/template 下的题目生成与测试模板，以及 leetcode/testutil 中更丰富的测试辅助函数，在本地批量验证自己的树形 DFS 实现。