题意概述

给定一个无向图，每条边有：

• 长度 $l$（影响通行时间）
• 海拔 $a$（影响洪水期的通行）

在水位线 $p$ 时，只能走海拔严格大于 $p$ 的边。

多组询问：从点 $u$ 出发，在水位 $p$ 下，开车到 $1$ 号点的最短步行距离（开车只能走海拔 $> p$ 的边，下车后步行走任意边）。

算法框架

1. 最短路预处理（Dijkstra）

inline void dijkstra() {
    // 计算从1号点到所有点的最短距离
    // 因为最终要回到1号点，所以反向思考：从1出发到各点的距离
}

• 计算从 1 号点 到所有点的最短路径长度 dis[i]
• 这样对于任意点 $u$，dis[u] 就是从 $u$ 步行到 1 号点的最短距离

2. Kruskal 重构树（按海拔构建最大生成树）

inline void kruskal() {
    sort(e + 1, e + 1 + m, cmp); // 按海拔降序排序
    // 构建重构树：新节点 tot 代表一条边，左右儿子是连通分量
}

• 按海拔从大到小排序边（最大生成树）
• 构建 Kruskal 重构树：
  • 新节点 tot 代表一条边，权值为该边海拔
  • 左右儿子 ls[tot], rs[tot] 代表两个连通分量
• 重构树性质：节点到根路径上的海拔权值递减

3. DFS 预处理重构树

void dfs(int u) {
    // 预处理倍增数组 f[u][i]
    // 计算 cost[u]：以 u 为根的子树中，所有原始节点到 1 号点的最小 dis 值
}

• 预处理倍增数组 f[u][i] 用于快速跳祖先
• cost[u] 表示：在重构树中，以 $u$ 为根的子树内，所有原始节点到 1 号点的最小 dis 值
  • 即：如果开车能到达这个子树，那么步行的最小距离就是 cost[u]

4. 在线查询处理

for (int i = 20; i >= 0; i--)
    if (val[f[u][i]] > p)
        u = f[u][i];
cout << cost[u] << endl;

查询 $(u, p)$：

1. 在重构树上从 $u$ 向上跳，找到海拔 > p 的最近祖先
2. 这个祖先的子树代表：从 $u$ 开车（经过海拔 > p 的边）能到达的所有点
3. 答案就是这个子树中所有点的最小 dis 值（即 cost[ancestor]）

关键技巧

1. 重构树的性质利用

• 重构树中，节点到根路径的边权递减（因为按海拔降序构建）
• 对于水位 $p$，从 $u$ 能开车到达的区域正好是：$u$ 的某个祖先的整个子树

2. cost 数组的意义

cost[u] = min(dis[u], min(cost[ls[u]], cost[rs[u]]))

• 叶子节点（原始节点）：cost[u] = dis[u]
• 内部节点（重构节点）：子树中的最小 dis 值

3. 倍增优化

• 预处理 f[u][i] 实现 $O(\log n)$ 的祖先跳跃
• 快速找到满足 val[ancestor] > p 的最高祖先

时间复杂度

• Dijkstra：$O(m \log m)$
• Kruskal：$O(m \log m)$
• DFS 预处理：$O(n \log n)$
• 每次查询：$O(\log n)$
• 总体：$O((m + q) \log n)$

总结

这个解法巧妙结合了：

1. 最短路：计算步行距离
2. Kruskal 重构树：处理海拔限制下的连通性
3. 树上倍增：快速定位满足条件的祖先
4. 子树最小值：预处理最优答案

是一个典型的 图论 + 数据结构 综合题，考察对多种算法的融合运用能力。