LeetCode 3241. 标记所有节点需要的时间 — Java 实现
题目概述
给定一棵无向树，节点编号 `0` 到 `n-1`。每个节点 `i` 被标记的规则：
- 奇数节点：相邻节点在时刻 `x-1` 被标记，则 `i` 在时刻 `x` 被标记（耗时 1）
- 偶数节点：相邻节点在时刻 `x-2` 被标记，则 `i` 在时刻 `x` 被标记（耗时 2）
求以每个节点为起点时，标记所有节点所需的最长时间。
核心思路
将问题转化为树形 DP + 换根（Re-rooting）：
1. 边权定义：从节点 `u` 到相邻节点 `v` 的"传播时间"取决于 `v` 的奇偶性
- `v` 为奇数：边权 = 1
- `v` 为偶数：边权 = 2
2. 两次 DFS：
- 第一次 DFS：计算每个节点子树内的最大深度和次大深度
- 第二次 DFS（换根）：计算每个节点往父节点方向的最长路径，得到最终答案
Java 实现
```java
class Solution {
private int[] ans;
// node[x][0] = 子树 x 的最大深度 mx1
// node[x][1] = 子树 x 的次大深度 mx2
// node[x][2] = 最大深度要往哪个儿子 my 走
private int[][] node;
public int[] timeTaken(int[][] edges) {
int n = edges.length + 1;
List<Integer>[] g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (int[] e : edges) {
int x = e[0], y = e[1];
g[x].add(y);
g[y].add(x);
}
ans = new int[n];
node = new int[n][3];
dfs(0, -1, g);
reroot(0, -1, 0, g);
return ans;
}
// 返回从 x 出发往子树方向的最大深度
private int dfs(int x, int fa, List<Integer>[] g) {
int mx1 = 0, mx2 = 0, my = 0;
for (int y : g[x]) {
if (y == fa) continue;
// 从 x 到 y 的边权: y 是偶数则 2, 奇数则 1
int depth = dfs(y, x, g) + 2 - y % 2;
if (mx1 < depth) {
mx2 = mx1;
mx1 = depth;
my = y;
} else if (mx2 < depth) {
mx2 = depth;
}
}
node[x][0] = mx1;
node[x][1] = mx2;
node[x][2] = my;
return mx1;
}
// from: 从 x 往父节点方向走的最长路径
private void reroot(int x, int fa, int from, List<Integer>[] g) {
ans[x] = Math.max(from, node[x][0]);
for (int y : g[x]) {
if (y != fa) {
// up1: 从 y 往上走到父节点 x 再继续往上
int up1 = from + 2 - x % 2;
// up2: 从 y 往上走到 x, 然后在 x 的其他子树中拐弯
int up2 = (y == node[x][2] ? node[x][1] : node[x][0]) + 2 - x % 2;
reroot(y, x, Math.max(up1, up2), g);
}
}
}
}
```
关键逻辑说明
变量 含义
`node[x][0]` 以 `x` 为根的子树中，往子树方向的最大深度
`node[x][1]` 以 `x` 为根的子树中，往子树方向的次大深度
`node[x][2]` 最大深度对应的子节点编号
`from` 从当前节点往父节点方向走的最长路径长度
`up1` 从子节点 `y` 往上经过 `x` 继续往上的路径
`up2` 从子节点 `y` 往上到 `x`，然后在 `x` 的其他子树中拐弯的路径
复杂度分析
- 时间复杂度：O(n)，每个节点访问常数次
- 空间复杂度：O(n)，递归栈和存储数组
示例验证
输入：`edges = [[0,1],[0,2]]`
- `i=0`：节点 1（奇数，耗时 1）→ `t=1`，节点 2（偶数，耗时 2）→ `t=2`，答案 = `2`
- `i=1`：节点 0（偶数，耗时 2）→ `t=2`，节点 2 需经过 0（偶数，耗时 2）→ `t=4`，答案 = `4`
- `i=2`：节点 0（偶数，耗时 2）→ `t=2`，节点 1（奇数，耗时 1）→ `t=3`，答案 = `3`
输出：`[2, 4, 3]` ✓
