题目分析

我们有 $m$ 棵相同的树，每棵树有 $n$ 个节点，相邻树之间相同编号的节点用蛛丝连接。需要处理 $q$ 次查询，求两点间的最短路径。

核心思路

问题转化

将问题转化为在扩展图上的最短路径问题：

• 每棵树内部的边权为原树边权
• 相邻树间相同节点的边权为 $a_x$

关键观察

1. 树间移动模式：蜘蛛在树间移动时，只会通过相同编号节点的蛛丝
2. 路径结构：最优路径形如：在起始树内移动 → 通过若干蛛丝跳跃 → 在目标树内移动
3. 对称性：由于所有树相同，问题可以规约到单棵树上的问题

算法架构

1. 凸包优化 (Convex Hull Trick)

代码中的 convex 类实现了李超线段树，用于维护一系列直线并快速查询最小值：

struct line {
    long long k, b;
    long long get(const int &x) const {
        return k * V[x] + b;
    }
};

应用场景：处理形如 $f(x) = k \cdot d + b$ 的线性函数最小值查询，其中 $d$ 是树间距离。

2. 树链剖分 (Heavy-Light Decomposition)

用于处理树上路径问题：

void dfs1(int u) {  // 计算子树大小、重儿子
void dfs2(int u, int tp) {  // 进行重链剖分
int LCA(int u, int v) {  // 求最近公共祖先

3. 线段树维护凸包

segment_tree 类将线段树与凸包结合，支持：

• 在特定区间插入线性函数
• 合并凸包
• 查询区间最小值

算法流程

预处理阶段

1. 树链剖分预处理

   • 计算每个节点的深度、父节点、子树大小
   • 确定重链，建立 DFS 序

2. 构建查询数据结构

   • 为每个节点预处理相关的轻子孙节点
   • 建立线段树结构

查询处理

对于查询 $(s, t)$：

1. 坐标转换：

   T.add_query(x % n, y % n, abs(x / n - y / n));
   

   将全局坐标转换为树内节点和树间距离

2. 路径分解：

   • 找到路径上的 LCA
   • 将路径分解为若干重链区间

3. 凸包查询：

   • 在相关区间查询线性函数最小值
   • 考虑四种情况（Q1-Q4）覆盖不同路径模式

4. 结果合并：

   for (int i = 0; i < idx; ++i) {
       ans[i] += sum[i];
   }
   

   将凸包查询结果与基础路径长度合并

关键技术点

1. 轻子孙优化

for (int u = 0; u < n; ++u) {
    lt[u].reserve(sz[u] - (son[u] == -1 ? 0 : sz[son[u]]));
}

为每个节点预分配轻子孙列表，优化内存访问。

2. 四种查询类型

• Q1：路径上的普通节点
• Q2：重链上的特殊处理
• Q3：LCA 节点的处理
• Q4：路径端点的特殊处理

3. 离散化优化

std::sort(V, V + pcnt);
pcnt = std::unique(V, V + pcnt) - V;

对树间距离进行离散化，减少凸包查询范围。

复杂度分析

• 预处理：$O(n \log n)$
• 每次查询：$O(\log^2 n)$（树链剖分 + 凸包查询）
• 总复杂度：$O(n \log n + q \log^2 n)$

适用数据范围

该算法能够处理题目中的最大数据范围：

• $n, q \leq 2 \times 10^5$
• $m \leq 10^9$（通过离散化处理）

总结

本题的解法体现了多个高级数据结构的综合运用：

1. 树链剖分处理树上路径
2. 凸包优化处理线性函数最值
3. 线段树维护区间信息
4. 离散化处理大范围查询参数

通过巧妙的问题转化和数据结构组合，在严格的时间限制内解决了大规模查询问题。