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

从 0 出发收集所有苹果再回来，最少走几秒

给一棵 n 个节点的无向树，也就是节点间只有连接、不分父子方向，edges 每一项是一条连着两个节点的边。hasApple 标出哪些节点上挂着苹果。人从节点 0 出发，把所有苹果都摘到、再回到 0，每经过一条边花 1 秒，问最少总秒数。题面这棵树 n=7，边是 [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]，苹果在节点 2、4、5，答案是 8 秒。

为什么不能把整棵树老老实实走一圈

把每个节点都逛一遍再回来，是立刻能想到的走法。可节点 3、6 没苹果、下面也没挂别的，专门拐进去摘个空再退出来，纯属白走两趟。真正要回答的不是怎么走遍，而是哪些边非走不可。

一条边到底走不走，只问它下方有没有苹果

判断一条边要不要走，只看它靠叶子那端的子树里有没有苹果：但凡有一个苹果，这条边就非走不可，不跨过它就够不着那个苹果；一个苹果都没有，整支跳过。有个容易漏的点——判断子树含不含苹果，节点自己也得算进去：节点 2 的孩子都空着，可它本身有苹果，通往它的边照样得走。

一条必经的边为什么是 2 秒不是 1 秒：去摘苹果走一趟，摘完还得原路回出发点，一来一回两趟。而「子树里有没有苹果」，得先把孩子全部递归算完才知道，所以用后序，孩子那几支的秒数先递归到手，这条边才判得清。无向边先建邻接表，每条边的两个端点互相记成邻居；往下走时用一个 vis 数组记谁进过，遇到已进过的邻居直接跳过，就不会从孩子绕回父亲。

每个节点交回一支的秒数，根 0 收成总答案

递归到节点 u 时，先把它每个没进过的邻居都往下算一遍，孩子交回的秒数累加成一笔和。接着分两种：节点 u 自己没苹果、孩子那边也一秒都没带回来，这笔和是 0，说明整支没苹果，返回 0，通往 u 的边等于没走；只要不为 0，这支就有苹果，返回「进入 u 那条边的 2 秒加上这笔和」。根 0 是出发点、没有父边，边成本记 0，它最终交出来的就是整棵树的答案。

顺着题面这棵树，8 秒是怎么攒出来的

从叶子那头往回结算。节点 4 有苹果，边 1-4 记 2 秒；节点 5 有苹果，边 1-5 记 2 秒。回到节点 1，它没苹果，但孩子带回 4 秒，子树确有苹果，边 0-1 再添 2 秒，这支合计 6 秒交给根。

另一边，节点 3、6 都没苹果、也没有孩子，各返回 0；可回到节点 2，它自己有一个苹果，边 0-2 照记 2 秒，这支是 2 秒。根 0 合起来 6 加 2 得 8 秒，正是题面要的 8。若苹果只在 2、5，少了 4 那条边，算下来是 6 秒。

边算成 1 秒、忘了拦父亲，答案就废了

一条必经的边算成 1 秒，总数会少一半——它是往返两趟。无向边只往孩子方向建、或递归时不拦父节点，会在父子间无限递归爆栈，双向建边加 vis 挡一下才行。最隐蔽的是判断子树时漏掉节点自己，边就被错误跳过。

复杂度上，建邻接表把每条边记两遍是 O(n)，后序里每个节点靠 vis 只进一次、每条边只碰常数次，时间 O(n)；邻接表、vis 数组、最坏整棵树连成一条链时的递归栈都是 O(n)，空间 O(n)。

Python

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)

C++

#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;
    }
};

Java

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;
    }
}