README_CN.md

1443. 收集树上所有苹果的最少时间

给你一棵有 n 个节点的无向树，节点编号为 0 到 n-1 ，它们中有一些节点有苹果。通过树上的一条边，需要花费 1 秒钟。你从 节点 0 出发，请你返回最少需要多少秒，可以收集到所有苹果，并回到节点 0 。

无向树的边由 edges 给出，其中 edges[i] = [fromi, toi] ，表示有一条边连接 from 和 toi 。除此以外，还有一个布尔数组 hasApple ，其中 hasApple[i] = true 代表节点 i 有一个苹果，否则，节点 i 没有苹果。

示例 1:

输入: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
输出: 8
解释: 上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。

示例 2:

输入: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
输出: 6
解释: 上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。

示例 3:

输入: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
输出: 0

提示:

• 1 <= n <= 105
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai < bi <= n - 1
• hasApple.length == n

题解 (Rust)

1. 题解

use std::collections::HashSet;

impl Solution {
    pub fn min_time(n: i32, edges: Vec<Vec<i32>>, mut has_apple: Vec<bool>) -> i32 {
        let n = n as usize;
        let mut children = vec![HashSet::new(); n];
        let mut parent = vec![n; n];
        let mut nodes = vec![0];

        for edge in &edges {
            children[edge[0] as usize].insert(edge[1] as usize);
            children[edge[1] as usize].insert(edge[0] as usize);
        }

        while let Some(node) = nodes.pop() {
            children[node].remove(&parent[node]);

            for &child in children[node].iter() {
                parent[child] = node;
                nodes.push(child);
            }
        }

        for node in 0..n {
            if children[node].is_empty() {
                nodes.push(node);
            }
        }

        while let Some(node) = nodes.pop() {
            if node == 0 {
                break;
            }

            has_apple[parent[node]] |= has_apple[node];
            children[parent[node]].remove(&node);
            if children[parent[node]].is_empty() {
                nodes.push(parent[node]);
            }
        }

        ((0..n).filter(|&node| has_apple[node]).count() as i32 - 1).max(0) * 2
    }
}