收集树上所有苹果的最少时间 图解题解

这道题到底在问什么

输入

苹果在 2、4、5

输出

8(走 4 条必经的边,每条来回 2 秒)

输入

苹果在 2、5

输出

6(只剩 3 条必经的边)

输入

没有任何苹果

输出

0(不用离开节点 0)

最优解：一步一步想明白

1. 3记牢两句:通往一个节点的边,只有它子树里有苹果才走;每条要走的边来回算 2 秒。后序就是先算孩子、再定自己这条边。下面每一帧都在套这条规则。
2. 4从节点 0 出发,苹果在 2、4、5先看清这棵树。紫色的节点 0 是出发点,也是最后要回到的地方。它的两个孩子是 1 和 2;节点 1 下面挂着 4 和 5,节点 2 下面挂着 3 和 6。苹果在节点 2、4、5。我们的目标是从 0 走出去,把这三个苹果都摘了,再回到 0,用的秒数越少越好。
3. 5边是无向的,从 0 当根定父子方向题目给的是无向边,要先建邻接表:每条边两个方向都记一遍。然后把节点 0 当根,从它出发往下走,沿途遇到的节点就成了孩子。走的时候要用一个标记记住谁已经访问过,这样就不会从孩子又走回父亲、绕回去。方向定好了,这棵树就有了上下层级。
4. 6子树有苹果才走这条边,一条边来回 2 秒动手前先把规则说死。第一,通往一个节点的边,要不要走,只看这个节点的子树里有没有苹果:有就必须走进去,没有就整支跳过。第二,凡是要走的边,都得算 2 秒,因为去摘苹果走一趟,摘完回出发点还要原路走回来,一条边来回两趟。带着这两条,开始后序搜索。
5. 7从根 0 开始往下探后序深度优先搜索从根 0 开始。蓝色表示这个节点已经进入、正挂在搜索路径上,但它的结果还没定。根没有父亲,所以没有进入它的边,根本身不产生秒数。先往它的第一个孩子 1 走下去。
6. 8走到节点 1,它自己没有苹果走到节点 1。它自己没有苹果,但现在还不能下结论,因为它下面还挂着 4 和 5,得先看孩子那边有没有苹果。继续往它的孩子里下探,先去 4。
7. 9节点 4 是叶子,且有苹果走到节点 4。它没有孩子,是个叶子,可以马上结算了。关键是:节点 4 上有苹果。子树里有苹果,那通往它的边就非走不可。
8. 104 有苹果,边 1-4 必须走,来回 2 秒结算节点 4:它有苹果,所以通往它的边 1-4 必须走。绿色代表这个节点的子树要去、它的那条边要计入。边 1-4 来回 2 秒记下来,累计变成 2 秒。节点 4 把 2 秒这个结果交回给父亲 1。接着看 1 的另一个孩子 5。
9. 11节点 5 是叶子,且有苹果走到节点 5,它也是叶子,同样可以直接结算。节点 5 上也有苹果,和 4 一样,通往它的边躲不掉。
10. 125 有苹果,边 1-5 必须走,再加 2 秒结算节点 5:有苹果,边 1-5 必须走,绿色标记,再加 2 秒,累计到 4 秒。现在节点 1 的两个孩子都看完了:4 带回 2 秒,5 带回 2 秒,合计 4 秒。回到节点 1,该决定它自己这条边了。
11. 13孩子带回 4 秒,节点 1 自己没苹果回到节点 1。它自己没有苹果,但它的孩子 4 和 5 带回来 4 秒,说明它的子树里确实有苹果要收。子树里有苹果,通往节点 1 的那条边 0-1 也得走。
12. 14子树 1 有苹果,边 0-1 走,子树 1 合计 6 秒结算节点 1:虽然它自己没苹果,但子树里有,所以通往它的边 0-1 也要走,再加 2 秒。节点 1 变绿。它把自己这条边的 2 秒,加上孩子带回的 4 秒,一共 6 秒交还给根 0。累计到 6 秒。现在回根 0,去看它的另一个孩子 2。
13. 15走到节点 2,它自己有苹果从根 0 走到另一个孩子 2。节点 2 自己有苹果,但先别急着结算,它下面还挂着 3 和 6,按后序还是要先把孩子看完。先去 3。
14. 16节点 3 是叶子,没有苹果走到节点 3,叶子,可以直接结算。节点 3 上没有苹果,它又没有孩子,子树里空空如也。
15. 173 子树无苹果,边 2-3 跳过,贡献 0结算节点 3:没有苹果,子树也没苹果,通往它的边 2-3 完全不用走。红色代表这条边跳过、贡献 0 秒。累计还是 6 秒不变。节点 3 把 0 交回给父亲 2。再看 2 的另一个孩子 6。
16. 18节点 6 是叶子,也没有苹果走到节点 6,也是叶子。它上面同样没有苹果,子树里也没有别的节点。和 3 一个情况。
17. 196 子树无苹果,边 2-6 跳过,贡献 0结算节点 6:没苹果,边 2-6 同样跳过,贡献 0 秒,标红。累计仍是 6 秒。现在节点 2 的两个孩子都看完了:3 带回 0,6 带回 0,孩子那边一个苹果都没有。回到节点 2 自己。
18. 20孩子带回 0 秒,但节点 2 自己有苹果回到节点 2。它的孩子 3、6 都没带回苹果,孩子方向是 0 秒。但别忘了一件事:节点 2 自己就有一个苹果!子树里有没有苹果,要把节点自己也算进去。所以子树 2 是有苹果的。
19. 21节点 2 自己有苹果,边 0-2 走,子树 2 合计 2 秒结算节点 2:因为它自己有苹果,通往它的边 0-2 必须走,加 2 秒。节点 2 变绿。它的两个孩子带回 0,所以子树 2 一共就是这 2 秒,交还给根 0。累计到 8 秒。注意这里的关键:哪怕孩子全没苹果,只要节点自己有,这条边照走。
20. 22两支孩子合计 6 + 2 = 8,根无父边最后回到根 0。它的两支孩子:节点 1 那支带回 6 秒,节点 2 那支带回 2 秒,合起来 8 秒。根 0 是出发点,没有进入它的父边,所以它自己不再添秒数。整棵树搜完,答案就是 8 秒。
21. 23计入的边: 1-4 / 1-5 / 0-1 / 0-2,各 2 秒回放一遍。真正走了的边只有 4 条:0-1、1-4、1-5、0-2,正好把节点 0 通向三个苹果 2、4、5 的路连起来。每条来回 2 秒,4 乘 2 等于 8。红色的 3 和 6 没苹果,通往它们的边 2-3、2-6 一步都没走,直接省掉。
22. 24节点 2 有苹果走 0-2,孩子 3、6 无苹果不走最后看一处最容易绕晕的地方。节点 2 的两个孩子 3、6 都没苹果,可通往 2 的边 0-2 照样走了,因为节点 2 自己有苹果。而通往 3、6 的边一条没走。这说明判断子树有没有苹果时,一定要把节点自己也数进去,不能只看孩子。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        def dfs(u, cost):
            if vis[u]:
                return 0
            vis[u] = True
            nxt_cost = 0
            for v in g[u]:
                nxt_cost += dfs(v, 2)
            if not hasApple[u] and nxt_cost == 0:
                return 0
            return cost + nxt_cost

        g = defaultdict(list)
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        vis = [False] * n
        return dfs(0, 0)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        vector<bool> vis(n);
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            int u = e[0], v = e[1];
            g[u].push_back(v);
            g[v].push_back(u);
        }
        return dfs(0, 0, g, hasApple, vis);
    }

    int dfs(int u, int cost, vector<vector<int>>& g, vector<bool>& hasApple, vector<bool>& vis) {
        if (vis[u]) return 0;
        vis[u] = true;
        int nxt = 0;
        for (int& v : g[u]) nxt += dfs(v, 2, g, hasApple, vis);
        if (!hasApple[u] && !nxt) return 0;
        return cost + nxt;
    }
};

import java.util.*;
class Solution {
    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
        boolean[] vis = new boolean[n];
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }
        return dfs(0, 0, g, hasApple, vis);
    }

    private int dfs(int u, int cost, List<Integer>[] g, List<Boolean> hasApple, boolean[] vis) {
        if (vis[u]) {
            return 0;
        }
        vis[u] = true;
        int nxtCost = 0;
        for (int v : g[u]) {
            nxtCost += dfs(v, 2, g, hasApple, vis);
        }
        if (!hasApple.get(u) && nxtCost == 0) {
            return 0;
        }
        return cost + nxtCost;
    }
}

复杂度

面试官可能追问