「PA 2019 Final」Zdjęcie rodzinne 题解

核心思路

1. 树结构分析

给定以 $1$ 为根的有根树，要求找到最长节点序列，使得任意相邻节点满足祖先-后代关系。

2. 序列性质

• 序列在树上形成一条可“拐弯”的路径
• 每次移动必须沿树边上下移动
• 可以在不同分支间跳跃，但跳跃点必须具有祖先关系

3. 状态定义

设 $f(u)$ 表示在 $u$ 的子树中，从 $u$ 开始的最长合法链长度。

4. 转移方程

对于节点 $u$，设其子节点集合为 $\text{children}(u)$：

$$f(u) = 1 + \sum_{v \in \text{children}(u)} \max(1, f(v) - 1) $$

解释：

• 基础值 $1$：包含节点 $u$ 本身
• 每个子节点 $v$ 至少贡献 $1$（直接连接）
• 如果 $f(v) > 1$，则额外贡献 $f(v) - 1$ 的长度

5. 答案计算

最终答案需要对所有节点 $u$ 计算：

$$\text{ans} = \max_{u \in V} \left(1 + \sum_{v \in \text{children}(u)} \max(1, f(v) - 1)\right) $$

特殊情况：当 $u$ 有多个子节点时，可以组合不同分支的链。

6. 贪心优化

• 对子节点按 $f(v)$ 值降序排序
• 优先处理能带来更大延伸的子节点
• 考虑多链组合的可能性

算法实现

1. 树构建

根据输入建立邻接表表示的树结构。

2. DFS 遍历

采用后序遍历计算每个节点的 $f(u)$ 值。

3. 全局维护

在 DFS 过程中维护全局最大值 $\text{ans}$。

4. 复杂度分析

• 时间复杂度：$O(n \log n)$（主要来自排序）
• 空间复杂度：$O(n)$