题目理解

我们有一棵以 $1$ 为根的有根树，支持两种操作：

1. 标记操作：给某个节点打上标记（一个节点可以被标记多次）
2. 询问操作：询问某个节点的最近标记祖先（包括自己）

关键点：

• 初始时只有根节点 $1$ 有标记
• 节点本身算作自己的祖先
• 标记操作是累积的（可以重复标记）

问题分析

暴力解法

对于每个询问，从该节点开始向上遍历直到找到第一个标记的祖先。

• 最坏情况：$O(n)$ 每次查询
• 总复杂度：$O(nq)$，对于 $n, q \leq 10^5$ 不可行

关键观察

我们需要支持两种操作：

• 更新：标记一个节点
• 查询：找某个节点的最近标记祖先

这类似于在树上的"最近标记祖先"查询问题。

解法思路

方法一：DFS序 + 线段树

核心思想：

• 对树进行DFS遍历，得到DFS序
• 每个节点对应一个区间 $[in[u], out[u]]$
• 标记操作相当于更新该节点为"已标记"
• 查询操作：在从根到该节点的路径上找最深的标记节点

算法步骤：

1. DFS预处理：

   • $in[u]$: 进入时间戳
   • $out[u]$: 离开时间戳
   • $depth[u]$: 节点深度
   • $parent[u]$: 父节点

2. 线段树维护：

   • 每个位置存储该DFS序位置对应的节点深度（如果被标记）
   • 查询时，在根到该节点的路径区间内找深度最大的标记节点

方法二：并查集优化

更巧妙的解法：使用类似"并查集"的结构，但方向相反。

核心思想：

• 维护 $fa[u]$ 表示节点 $u$ 的最近标记祖先
• 初始时所有 $fa[u] = 1$（因为只有根节点有标记）
• 标记节点 $u$ 时，让 $u$ 的子树中所有节点的 $fa[v]$ 更新为 $u$（如果 $u$ 比原来的 $fa[v]$ 更近）

优化： 使用DFS序 + 线段树可以高效实现子树更新。

方法三：离线处理 + 栈

算法流程：

1. 读取所有操作
2. 按DFS顺序处理，维护一个标记节点的栈
3. 遇到标记操作时入栈
4. 遇到查询操作时，栈顶就是最近标记祖先

## 算法复杂度分析

- **DFS预处理**：$O(n)$
- **线段树构建**：$O(n)$
- **每次标记操作**：$O(\log n)$
- **每次查询操作**：$O(\log n)$
- **总复杂度**：$O(n + q \log n)$

## 关键技巧总结

1. **DFS序转化**：将树结构转化为线性序列，便于使用线段树
2. **路径查询技巧**：根到节点 $u$ 的路径对应区间 $[1, in[u]]$
3. **最大深度维护**：通过维护深度信息来找到"最近"的祖先
4. **线段树应用**：高效处理区间最大值查询和单点更新

## 正确性证明

对于查询节点 $u$：
- 根到 $u$ 的路径上的所有节点对应的DFS序都在 $[1, in[u]]$ 范围内
- 线段树维护了这个区间内标记节点的最大深度
- 深度最大的标记节点就是最近的标记祖先
- 由于节点本身也算祖先，如果 $u$ 被标记，它自己就是答案


这种方法充分利用了树的DFS序性质，将复杂的树上路径查询转化为高效的区间查询问题，实现了对数级别的时间复杂度。