3241. 标记所有节点所需的时间

Hard

题目描述

有一个由 n 个节点组成的无向树，节点编号从 0 到 n - 1。给定一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。

初始时，所有节点都未被标记。对于每个节点 i：

如果 i 是奇数，当至少有一个与它相邻的节点在时间 x - 1 被标记时，节点 i 将在时间 x 被标记。
如果 i 是偶数，当至少有一个与它相邻的节点在时间 x - 2 被标记时，节点 i 将在时间 x 被标记。

返回一个数组 times，其中 times[i] 是当你在时间 t = 0 标记节点 i 时，树中所有节点被标记的时间。

注意每个 times[i] 的答案是独立的，即当你标记节点 i 时，所有其他节点都未被标记。

示例 1：

输入：edges = [[0,1],[0,2]]
输出：[2,4,3]
解释：
- i = 0：节点 1 在 t = 1 被标记，节点 2 在 t = 2 被标记。
- i = 1：节点 0 在 t = 2 被标记，节点 2 在 t = 4 被标记。
- i = 2：节点 0 在 t = 2 被标记，节点 1 在 t = 3 被标记。

示例 2：

输入：edges = [[0,1]]
输出：[1,2]

示例 3：

输入：edges = [[2,4],[0,1],[2,3],[0,2]]
输出：[4,6,3,5,5]

约束条件：

2 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= edges[i][0], edges[i][1] <= n - 1
输入保证 edges 表示一个有效的树

解题思路

这道题需要使用树形 DP 和换根 DP 技巧来解决。

核心思路：

理解标记规则：奇数节点需要等待 1 个时间单位，偶数节点需要等待 2 个时间单位。这意味着从一个节点传播到相邻节点的时间取决于目标节点的奇偶性。
树形 DP：对于每个节点作为根时，我们需要计算从该根开始标记所有节点的最长时间。这可以通过 DFS 计算每个子树的深度来实现。
换根 DP 优化：朴素方法是对每个节点都做一次 DFS，时间复杂度为 O(n²)。我们可以使用换根 DP 技巧，先以任意节点为根计算所有子树信息，然后通过一次 DFS 传递根节点变化的影响，将复杂度降到 O(n)。

算法步骤：

构建邻接表表示树
第一次 DFS：以节点 0 为根，计算每个节点向下的最大传播时间，并记录每个节点的最长和次长子树路径
第二次 DFS：换根处理，计算每个节点作为根时的答案，考虑来自父节点方向的贡献

时间计算：从节点 u 传播到节点 v 需要的时间是 v % 2 == 1 ? 1 : 2。

代码实现

class Solution {
public:
    vector<int> timeTaken(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector<vector<int>> adj(n);
        
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        
        vector<int> ans(n);
        vector<int> max1(n, 0), max2(n, 0);
        
        function<int(int, int)> dfs1 = [&](int u, int parent) -> int {
            for (int v : adj[u]) {
                if (v != parent) {
                    int time = dfs1(v, u) + (v % 2 == 1 ? 1 : 2);
                    if (time > max1[u]) {
                        max2[u] = max1[u];
                        max1[u] = time;
                    } else if (time > max2[u]) {
                        max2[u] = time;
                    }
                }
            }
            return max1[u];
        };
        
        function<void(int, int, int)> dfs2 = [&](int u, int parent, int fromParent) {
            ans[u] = max(max1[u], fromParent);
            
            for (int v : adj[u]) {
                if (v != parent) {
                    int childTime = max1[v] + (v % 2 == 1 ? 1 : 2);
                    int toChild = (childTime == max1[u] ? max2[u] : max1[u]);
                    toChild = max(toChild, fromParent) + (u % 2 == 1 ? 1 : 2);
                    dfs2(v, u, toChild);
                }
            }
        };
        
        dfs1(0, -1);
        dfs2(0, -1, 0);
        
        return ans;
    }
};

class Solution:
    def timeTaken(self, edges: List[List[int]]) -> List[int]:
        n = len(edges) + 1
        adj = [[] for _ in range(n)]
        
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        
        ans = [0] * n
        max1 = [0] * n
        max2 = [0] * n
        
        def dfs1(u, parent):
            for v in adj[u]:
                if v != parent:
                    time = dfs1(v, u) + (1 if v % 2 == 1 else 2)
                    if time > max1[u]:
                        max2[u] = max1[u]
                        max1[u] = time
                    elif time > max2[u]:
                        max2[u] = time
            return max1[u]
        
        def dfs2(u, parent, from_parent):
            ans[u] = max(max1[u], from_parent)
            
            for v in adj[u]:
                if v != parent:
                    child_time = max1[v] + (1 if v % 2 == 1 else 2)
                    to_child = max2[u] if child_time == max1[u] else max1[u]
                    to_child = max(to_child, from_parent) + (1 if u % 2 == 1 else 2)
                    dfs2(v, u, to_child)
        
        dfs1(0, -1)
        dfs2(0, -1, 0)
        
        return ans

public class Solution {
    public int[] TimeTaken(int[][] edges) {
        int n = edges.Length + 1;
        var adj = new List<int>[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }
        
        var ans = new int[n];
        var max1 = new int[n];
        var max2 = new int[n];
        
        int Dfs1(int u, int parent) {
            foreach (int v in adj[u]) {
                if (v != parent) {
                    int time = Dfs1(v, u) + (v % 2 == 1 ? 1 : 2);
                    if (time > max1[u]) {
                        max2[u] = max1[u];
                        max1[u] = time;
                    } else if (time > max2[u]) {
                        max2[u] = time;
                    }
                }
            }
            return max1[u];
        }
        
        void Dfs2(int u, int parent, int fromParent) {
            ans[u] = Math.Max(max1[u], fromParent);
            
            foreach (int v in adj[u]) {
                if (v != parent) {
                    int childTime = max1[v] + (v % 2 == 1 ? 1 : 2);
                    int toChild = (childTime == max1[u] ? max2[u] : max1[u]);
                    toChild = Math.Max(toChild, fromParent) + (u % 2 == 1 ? 1 : 2);
                    Dfs2(v, u, toChild);
                }
            }
        }
        
        Dfs1(0, -1);
        Dfs2(0, -1, 0);
        
        return ans;
    }
}

var timeTaken = function(edges) {
    const n = edges.length + 1;
    const graph = Array(n).fill().map(() => []);
    
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const result = [];
    
    for (let start = 0; start < n; start++) {
        const times = Array(n).fill(-1);
        times[start] = 0;
        
        let changed = true;
        let time = 1;
        
        while (changed) {
            changed = false;
            
            for (let node = 0; node < n; node++) {
                if (times[node] !== -1) continue;
                
                const delay = node % 2 === 0 ? 2 : 1;
                
                for (const neighbor of graph[node]) {
                    if (times[neighbor] === time - delay) {
                        times[node] = time;
                        changed = true;
                        break;
                    }
                }
            }
            
            time++;
        }
        
        result.push(Math.max(...times));
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	分析
时间复杂度	O(n)
空间复杂度	O(n)

时间复杂度：两次 DFS 遍历，每次访问每个节点一次，总时间复杂度为 O(n)
空间复杂度：需要存储邻接表 O(n)、递归栈深度最多 O(n)，辅助数组 O(n)，总空间复杂度为 O(n)

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目