解题思路

先推一下我的全文站内跳转

对于“紧急集合”这道题目，核心问题是在一棵树（n个节点，n-1条边，连通无环）上，处理多次查询（m次）。每次查询给定三个节点x、y、z，需要找到一个集结点p，使得从x、y、z到p的总距离（即路径长度之和）最小，并输出p和最小总距离c。

关键知识点

树的性质：

• 树是无向无环连通图，任意两点间有唯一路径。
• 路径长度（距离）可以通过节点的深度（从根节点开始的边数）和最近公共祖先（LCA）计算。

最优集结点p的确定：

对于三个点x、y、z，最优集结点p是它们两两LCA（LCA(x,y)、LCA(y,z)、LCA(z,x)）中深度最大的那个。这是因为深度最大的LCA位于三个点路径的交汇处，能最小化总距离。

最小总距离c的计算：

最小总距离c可以通过三个两两点对的距离之和除以2得到，即： [ c = \frac{2 \times \text{dist}(x,y) + \text{dist}(y,z) + \text{dist}(z,x)}{2} ] 其中，(\text{dist}(a,b)) 是节点a和b之间的距离，计算公式为： [ \text{dist}(a,b) = \text{depth}[a] + \text{depth}[b] - 2 \times \text{depth}[\text{LCA}(a,b)] ] 这里，(\text{depth}[u]) 表示节点u的深度（以固定根节点为基准）。

高效查询LCA：

由于n和m最大可达5×10⁵，直接遍历树计算LCA会超时。需要使用倍增法预处理树，实现O(log n)时间复杂度的LCA查询。倍增法通过预计算节点的2^k级祖先表，加速LCA查询。

整体流程

预处理阶段：

• 以节点1为根，DFS遍历树计算深度和直接父节点，然后构建倍增表（存储每个节点的2^k级祖先）。

查询阶段：

• 对于每个查询(x, y, z)：
  • 计算三个两两LCA： lca_xy = LCA(x,y), lca_yz = LCA(y,z), lca_zx = LCA(z,x)。
  • 找出深度最大的LCA作为p。
  • 计算两两点对距离： dist_xy = dist(x,y), dist_yz = dist(y,z), dist_zx = dist(z,x)。
  • 计算c = (dist_xy + dist_yz + dist_zx) / 2（c为整数）。
  • 输出p和c。

时间复杂度：

• 预处理O(n log n)，每个查询O(log n)，总O(n log n + m log n)，符合约束。

为什么这个方法正确？

• p的选择：深度最大的LCA是三个点路径的“中心”，确保总距离最小（数学归纳和树的性质证明）。
• 距离公式：基于深度和LCA，避免显式计算路径，效率高。
• 优化：直接使用两两点对距离求和除以2，避免额外计算到p的距离。

看到这里应该思路都有了吧！祝你AC