题目理解

我们需要在树上从起点 $s$ 出发，每一步必须移动到相邻节点，每到一个节点（包括起点）先加上该节点的权值 $w_i \in \{1,-1\}$，然后检查：

1. 当前生命值 $S$ 是否等于 $0$（死亡）
2. 当前节点是否被熔岩淹没（即当前时刻 $t \ge$ 该节点到根的距离）

如果满足任一条件，则立即死亡。我们要求最大移动步数（即到达某个节点并执行权值加法后死亡，或者被熔岩淹没前的最后一步）。

---

核心观察

1. 熔岩淹没条件

设 $d_u$ 为节点 $u$ 到根的距离（根为 $1$）。在时刻 $t$，所有满足 $d_u \le t$ 的节点 $u$ 会被淹没。

因此，如果你在时刻 $t$ 到达节点 $u$，则：

• 如果 $d_u \le t$，则你立即被淹死（在移动后的那个时刻检查）。
• 否则暂时安全。

2. 生命值变化

初始 $S = 1$，每到一个节点 $u$，生命值变为 $S + w_u$。因为 $w_u = \pm 1$，所以生命值每次只能变化 $\pm 1$，且永远不能等于 $0$ 否则死亡。

这意味着：生命值 $S$ 永远为正整数（如果死亡则过程结束）。

3. 关键转化

设 $P$ 是从起点到当前节点的路径（允许重复节点），则当前生命值 $S = 1 + \sum_{v \in P} w_v$。

由于 $S > 0$，我们有：

$$\sum_{v \in P} w_v \ge 0$$

且 $S \neq 0$ 自动满足。

---

最优策略的性质

4. 熔岩时间约束

设当前时间是 $t$（已经走了 $t$ 步），你位于节点 $u$，那么必须满足：

$$d_u > t$$

否则死亡。

另外，你在节点 $u$ 加完 $w_u$ 后，必须马上移动到邻居（不能停留）。所以时间 $t$ 与步数一致（第 $t$ 步结束时时刻为 $t$）。

5. 死亡原因

可能死在两种情况下：

1. 生命值归零：路径权值累积和恰好达到 $-1$（因为初始是 $1$）。
2. 被熔岩淹没：到达节点 $u$ 时 $d_u \le t$，且这一步结束后检查。

---

标程思路

6. 预处理：最早被淹时间

标程先计算 $d_u$（getdis），然后用 BFS 求每个节点的 tim[u]：

• tim[u] 表示从某个“好结构”开始，到该节点被淹的最早时刻。
• 初始队列放入所有 $w_i = 1$ 且邻居也有 $w=1$ 的节点（即连在一起的 $+1$ 块边界），设置 tim[i] = 0。
• BFS 时，当从 $u$ 走到 $v$ 且 $w_u \neq w_v$ 时，tim[v] = tim[u] + 1。

含义：tim[u] 代表如果从某个 $+1$ 块边界出发，经过交替符号的路径到达 $u$，所需的最小时间（即被淹的时间）。这与熔岩蔓延有关。

7. DFS 搜索可行路径

函数 dfs(u, fa, k, inn, hei, TIM, dis)：

• $u$：当前节点
• $k$：当前允许的最大负积累（与 tim 相关）
• inn：是否处于“内部”状态（标记路径是否已经交替符号）
• hei：当前生命值 $-1$？实际上 hei 是当前累积和？需要看代码：
  • 初始调用 dfs(st, -1, tim[st], 1, w[st], 1, 1)
  • hei 初始为 $w[st] = 1$，TIM=1，dis=1。
  • 在 dfs 内：如果 hei < 0，则更新 TIM = max(TIM, (-hei+1)/2*2 + k*2 + dis)。这像是在计算当生命值降到负数时，如何延长存活时间。
  • 如果 TIM <= dist[u]，则 ans = max(ans, dist[u])，否则 return（无法到达）。

这个 DFS 实际上是在模拟能够安全到达的最深深度 dist[u]（到根的距离），并记录最大值。

8. 最终答案

最后输出 ans + (dist[st] & 1) - 1。

• dist[st] & 1 是起点深度的奇偶性调整。
• 减 $1$ 是因为步数比时间多 1？需要结合例子验证。

从第一个样例： 起点 $st=4$，$dist[4]=3$，输出 $6$。$ans$ 计算的是最深的可达 dist[u]，比如到达 $u=7$ 时 $dist[7]=6$，ans=6，然后 $6 + (3\&1)-1 = 6+1-1=6$。

---

核心结论

这个题的本质是：在树上行走，保证生命值一直为正，且不能进入已被熔岩淹没的区域。熔岩从根以速度 $1$ 向外蔓延。

最优策略通常是：

1. 尽可能远离根（增加 $dist$），因为这样不容易被淹。
2. 同时要维持生命值，所以需要走在 $w=1$ 的节点上积累生命值，偶尔通过 $w=-1$ 的节点转向。
3. tim[u] 表示从某个 $+1$ 块出发，经过交替符号到达 $u$ 的最小时间，这决定了你是否能在被淹前到达 $u$。

DFS 相当于模拟所有可能的安全路径，取最大的 $dist[u]$ 作为可达深度，最后转换成步数。

---

时间复杂度

• 预处理 $dist$：$O(n)$
• BFS 求 tim：$O(n)$
• DFS 遍历：每个节点访问常数次，总 $O(n)$
• 总复杂度 $O(\sum n)$，满足 $10^6$ 限制。

---

总结

标程通过：

• 熔岩时间 转化为节点安全时间约束
• 生命值 转化为路径权值和约束
• 用 tim 数组标记可安全到达的时间窗口
• DFS 搜索最深可到的深度
• 最后通过奇偶调整得到最大步数

这题结合了 树上 BFS、路径约束 和 时间依赖的安全区域，是一道较复杂的树形 DP / 搜索优化题。