题解：Dreaming Is Not Harmful

题目分析

核心规则

1. 公司结构是以 $1$ 为根的树，员工 $v$ 的直属上级是 $p_v$，能力值 $s_v$ 互不相同，值越大能力越强。
2. 每日淘汰规则：根节点（CEO）被开除，能力最强的直接子节点继任为新根，原根的其他子节点成为新根的直接子节点。
3. 每个员工 $v$ 能算出不取消任何人时自己成为 CEO 的天数 $t_v$。
4. 询问：对 $v_k$，恰好取消一个员工（将其 $s$ 置 $0$），求 $v_k$ 成为 CEO 的最小天数。
5. 所有询问独立，不修改原始数据。

关键观察

1. 继任顺序完全由能力值排序决定：每天淘汰当前根，下一个根是当前根的最大 $s$ 子节点。
2. 设全局能力降序排列为 $u_1, u_2, \ldots, u_n$（$s_{u_1} > s_{u_2} > \ldots > s_{u_n}$），则：
   • 第 $1$ 天 CEO：$u_1$
   • 第 $2$ 天 CEO：$u_2$
   • $\ldots$
   • 第 $k$ 天 CEO：$u_k$ 因此原始天数 $t_v = \text{rank}(v) - 1$（$\text{rank}(v)$ 是 $v$ 在全局降序中的排名）。
3. 取消一个员工 $x$，等价于删除 $x$，新的继任序列是原序列去掉 $x$，新天数 $t'_v = \text{new\_rank}(v) - 1$。
4. 目标：对 $v$，选一个 $x$ 删除，使得 $\text{new\_rank}(v)$ 最小，即 $t'_v$ 最小。

---

核心转化

设 $R(v)$ 为 $v$ 在原始能力降序中的排名，则：

• 不删除时：$\text{ans} = R(v) - 1$
• 删除 $x$ 时：
  • 若 $x$ 在 $v$ 之前（$R(x) < R(v)$）：$\text{new\_rank}(v) = R(v) - 1$，$\text{ans} = R(v) - 2$
  • 若 $x$ 在 $v$ 之后（$R(x) > R(v)$）：$\text{new\_rank}(v) = R(v)$，$\text{ans} = R(v) - 1$
  • 若 $x = v$：无效（取消自己无法成为 CEO）

终极结论

对询问 $v$：

1. 若 $v = 1$（根节点）：答案为 $0$。
2. 否则：
   • 若存在至少一个节点 $x$，满足 $R(x) < R(v)$，且 $x$ 在 $v$ 的「继任依赖链」上：答案为 $R(v) - 2$。
   • 否则：答案为 $R(v) - 1$。

---

树的继任依赖链（关键定义）

一个节点 $x$ 能阻碍 $v$ 快速继任，当且仅当 $x$ 是 $v$ 到根的路径上，在原始继任过程中，会比 $v$ 先成为根的节点。

简化：对每个节点 $v$，定义前驱集合 $P(v)$：所有满足 $R(x) < R(v)$，且 $x$ 是 $v$ 的祖先（含父节点、根）的节点。

• 若 $P(v) \neq \emptyset$：删除 $P(v)$ 中任意一个 $x$，$v$ 的排名提前 $1$，答案 $= R(v) - 2$。
• 若 $P(v) = \emptyset$：无法提前，答案 $= R(v) - 1$。

---

算法步骤

步骤1：预处理排名

1. 读取树结构、能力值 $s$。
2. 对所有节点按 $s$降序排序，得到排名数组 $\text{rank}[1 \ldots n]$（$\text{rank}[v]$ 为 $v$ 的排名）。

步骤2：预处理祖先的最小排名

对每个节点 $v$，维护从根到 $v$ 的路径上，最小的 rank 值（记为 $\text{min\_anc\_rank}[v]$）：

$$\text{min\_anc\_rank}[v] = \min(\text{rank}[v], \text{min\_anc\_rank}[p_v]) $$

步骤3：回答询问

对每个询问 $v$：

1. 若 $v = 1$：输出 $0$。
2. 否则：
   • 若 $\text{min\_anc\_rank}[p_v] < \text{rank}[v]$：说明存在祖先 $x$ 满足 $R(x) < R(v)$，答案 $= \text{rank}[v] - 2$。
   • 否则：答案 $= \text{rank}[v] - 1$。

---

复杂度分析

• 排序：$O(n \log n)$
• 遍历树预处理 $\text{min\_anc\_rank}$：$O(n)$
• 回答询问：$O(q)$

总复杂度：$O(n \log n + q)$，完全满足 $n, q \leq 3 \times 10^5$ 的约束。

---

总结

1. 核心：继任顺序 = 能力值降序，天数 = 排名 $-$ 1。
2. 取消一个节点的最优选择：删除排名比 $v$ 靠前的祖先，让 $v$ 排名提前 $1$。
3. 算法线性遍历 + 排序，高效处理大数据量。