「ROI 2025 Day1 T4」树上的青蛙 题解

题目大意

给定一棵 $n$ 个节点的树，每个节点有一只青蛙，初始为绿色。青蛙每次沿边跳到相邻节点会变色（绿↔棕）。一只青蛙可以跳到另一只青蛙所在节点组成一对，要求：

• 跳跃次数 ≤ $d$（输入给定的奇数）
• 跳跃次数必须是奇数（保证到达时颜色相反）
• 每只青蛙只能加入一对

目标是找到最大配对数，并输出具体配对方案。

解题思路

核心观察

1. 颜色变化规律：青蛙每跳一次颜色反转，因此经过奇数步后颜色会与初始相反
2. 奇偶性匹配：要组成一对（颜色不同），两只青蛙的初始深度必须具有相同的奇偶性
3. 距离限制：只能在距离 ≤ $d$ 的范围内寻找配对伙伴

算法框架

预处理阶段

• 进行 DFS 计算每个节点的深度和子树大小
• 标记每个节点的重儿子（子树最大的儿子）

集合维护

每个节点维护两个集合：

• 深度为偶数的节点集合
• 深度为奇数的节点集合

集合中存储 (-深度, 节点ID) 对，便于后续的范围查询和匹配。

匹配策略

1. 插入节点时立即匹配：当向集合中插入新节点时，立即在相反奇偶性的集合中查找可能的匹配伙伴
2. 距离检查：通过深度差和设定的距离公式，快速判断两个节点是否能在 $d$ 步内相遇
3. 贪心原则：一旦发现可以匹配的节点对，就立即进行匹配

启发式合并

• 先递归处理重儿子，直接继承其集合（$O(1)$ 交换）
• 再处理轻儿子，将它们的集合合并到当前节点集合中
• 在合并过程中持续进行匹配检查

关键技巧

1. 深度记录：维护 node[] 数组记录每个深度对应的节点，便于快速定位
2. 延迟删除：匹配成功后从集合中删除已配对的节点
3. 范围查询：使用 lower_bound 在集合中快速查找满足距离约束的节点

输出方案

算法不仅计算最大匹配数，还记录具体的配对方案。当发现可匹配的节点对时：

• 标记两个节点为已匹配
• 将配对信息加入答案列表
• 从集合中删除这两个节点

算法优势

1. 高效性：利用启发式合并保证总复杂度为 $O(n \log^2 n)$
2. 完整性：能够处理大规模数据（$n \leq 5 \times 10^5$）
3. 实用性：输出具体配对方案，满足题目满分要求

总结

本题通过巧妙的奇偶性分析和树上启发式合并技术，解决了树上带约束的最大匹配问题。算法在保证正确性的同时，能够高效处理大规模输入，并输出具体的配对方案。

算法标签：树上启发式合并 贪心匹配 奇偶性分析 集合维护