列表

详情

100392. 标记所有节点需要的时间

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

一开始，所有 节点都 未标记 。对于节点 i ：

请你返回一个数组 times ，表示如果你在时刻 t = 0 标记节点 i ，那么时刻 times[i] 时，树中所有节点都会被标记。

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

 

示例 1：

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

输出：[2,4,3]

解释：

示例 2：

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

输出：[1,2]

解释：

示例 3：

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

输出：[4,6,3,5,5]

解释：

 

提示：

相似题目

树中距离之和

树上最大得分和路径

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> timeTaken(vector<vector<int>>& edges) { } };

golang 解法, 执行用时: 423 ms, 内存消耗: 41.7 MB, 提交时间: 2024-08-10 12:05:48 

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

	// nodes[x] 保存子树 x 的最大深度 maxD，次大深度 maxD2，以及最大深度要往儿子 y 走
	nodes := make([]struct{ maxD, maxD2, y int }, len(g))
	var dfs func(int, int) int
	dfs = func(x, fa int) int {
		p := &nodes[x]
		for _, y := range g[x] {
			if y == fa {
				continue
			}
			maxD := dfs(y, x) + 2 - y%2 // 从 x 出发，往 y 方向的最大深度
			if maxD > p.maxD {
				p.maxD2 = p.maxD
				p.maxD = maxD
				p.y = y
			} else if maxD > p.maxD2 {
				p.maxD2 = maxD
			}
		}
		return p.maxD
	}
	dfs(0, -1)

	ans := make([]int, len(g))
	var reroot func(int, int, int)
	reroot = func(x, fa, fromUp int) {
		p := nodes[x]
		ans[x] = max(fromUp, p.maxD)
		for _, y := range g[x] {
			if y == fa {
				continue
			}
			w := 2 - x%2 // 从 y 到 x 的边权
			if y == p.y { // 对于 y 来说，上面要选次大的
				reroot(y, x, max(fromUp, p.maxD2)+w)
			} else { // 对于 y 来说，上面要选最大的
				reroot(y, x, max(fromUp, p.maxD)+w)
			}
		}
	}
	reroot(0, -1, 0)
	return ans
}

python3 解法, 执行用时: 1194 ms, 内存消耗: 97.7 MB, 提交时间: 2024-08-10 12:05:29 

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

        # nodes[x] 保存子树 x 的最大深度 max_d，次大深度 max_d2，以及最大深度要往儿子 my 走
        nodes = [None] * len(g)
        def dfs(x: int, fa: int) -> int:
            max_d = max_d2 = my = 0
            for y in g[x]:
                if y == fa:
                    continue
                depth = dfs(y, x) + 2 - y % 2  # 从 x 出发，往 my 方向的最大深度
                if depth > max_d:
                    max_d2 = max_d
                    max_d = depth
                    my = y
                elif depth > max_d2:
                    max_d2 = depth
            nodes[x] = (max_d, max_d2, my)
            return max_d
        dfs(0, -1)

        ans = [0] * len(g)
        def reroot(x: int, fa: int, from_up: int) -> None:
            max_d, max_d2, my = nodes[x]
            ans[x] = max(from_up, max_d)
            w = 2 - x % 2  # 从 y 到 x 的边权
            for y in g[x]:
                if y != fa:
                    reroot(y, x, max(from_up, max_d2 if y == my else max_d) + w)
        reroot(0, -1, 0)
        return ans

java 解法, 执行用时: 195 ms, 内存消耗: 120.6 MB, 提交时间: 2024-08-10 12:05:17 

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

        // nodes[x] 保存子树 x 的最大深度 maxD，次大深度 maxD2，以及最大深度要往儿子 my 走
        int[][] nodes = new int[g.length][3];
        dfs(0, -1, g, nodes);

        int[] ans = new int[g.length];
        reroot(0, -1, 0, g, nodes, ans);
        return ans;
    }

    private int dfs(int x, int fa, List<Integer>[] g, int[][] nodes) {
        int maxD = 0;
        int maxD2 = 0;
        int my = 0;
        for (int y : g[x]) {
            if (y == fa) {
                continue;
            }
            int depth = dfs(y, x, g, nodes) + 2 - y % 2; // 从 x 出发，往 my 方向的最大深度
            if (depth > maxD) {
                maxD2 = maxD;
                maxD = depth;
                my = y;
            } else if (depth > maxD2) {
                maxD2 = depth;
            }
        }
        nodes[x][0] = maxD;
        nodes[x][1] = maxD2;
        nodes[x][2] = my;
        return maxD;
    }

    private void reroot(int x, int fa, int fromUp, List<Integer>[] g, int[][] nodes, int[] ans) {
        int maxD = nodes[x][0];
        int maxD2 = nodes[x][1];
        int my = nodes[x][2];
        ans[x] = Math.max(fromUp, maxD);
        for (int y : g[x]) {
            if (y != fa) {
                reroot(y, x, Math.max(fromUp, (y == my ? maxD2 : maxD)) + 2 - x % 2, g, nodes, ans);
            }
        }
    }
}

cpp 解法, 执行用时: 770 ms, 内存消耗: 314.8 MB, 提交时间: 2024-08-10 12:05:01 

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

        // nodes[x] 保存子树 x 的最大深度 max_d，次大深度 max_d2，以及最大深度要往儿子 my 走
        vector<tuple<int, int, int>> nodes(g.size());
        auto&& dfs = [&](auto&& dfs, int x, int fa) -> int {
            int max_d = 0, max_d2 = 0, my = 0;
            for (int y : g[x]) {
                if (y == fa) {
                    continue;
                }
                int depth = dfs(dfs, y, x) + 2 - y % 2; // 从 x 出发，往 my 方向的最大深度
                if (depth > max_d) {
                    max_d2 = max_d;
                    max_d = depth;
                    my = y;
                } else if (depth > max_d2) {
                    max_d2 = depth;
                }
            }
            nodes[x] = {max_d, max_d2, my};
            return max_d;
        };
        dfs(dfs, 0, -1);

        vector<int> ans(g.size());
        auto&& reroot = [&](auto&& reroot, int x, int fa, int from_up) -> void {
            auto& [max_d, max_d2, my] = nodes[x];
            ans[x] = max(from_up, max_d);
            for (int y : g[x]) {
                if (y != fa) {
                    reroot(reroot, y, x, max(from_up, (y == my ? max_d2 : max_d)) + 2 - x % 2);
                }
            }
        };
        reroot(reroot, 0, -1, 0);
        return ans;
    }
};

上一题

© 2024 leetcode.cn