【题目描述】给出 n 个点的一棵树多次询问两点之间的最短距离。注意边是双向的。【输入】第一行为两个整数 n 和 m。n 表示点数m 表示询问次数下来 n−1 行每行三个整数 x,y,k表示点 x 和点 y 之间存在一条边长度为 k再接下来 m 行每行两个整数 x,y表示询问点 x 到点 y 的最短距离。【输出】输出 m 行。对于每次询问输出一行。【输入样例】2 2 1 2 100 1 2 2 1【输出样例】100 100【提示】样例输入 23 2 1 2 10 3 1 15 1 2 3 2样例输出 210 25数据范围与提示对于全部数据2≤n≤10^4,1≤m≤2×10^4,0k≤100,1≤x,y≤n。在树论算法中求解树上任意两点之间的距离是一个经典且高频的考点。无论是初学者打基础还是在正式竞赛中作为复杂题目的一个底层模块掌握它都至关重要。本文将从最核心的数学转换入手深度剖析如何通过两种截然不同的降维打击手段——“倍增法”与“欧拉序 RMQ”来解决带权树上的距离查询问题。一、 题目分析与核心思路题目核心给定一棵包含 n 个节点的无根树节点间有权值以及 m 次查询。每次查询要求输出给定的两点 x 和 y 之间的最短路径距离。 数据范围n≤10^4m≤2×10^4。思考过程数学转换在树形结构中任意两点 x 和 y 之间的唯一简单路径必然会经过它们的最近公共祖先LCA。 如果在遍历树的时候我们预处理出每个节点到根节点的物理距离记为dis[i]那么 x 到 y 的距离公式可以完美转化为差分形式Distance(x,y)dis[x]dis[y]−2×dis[LCA(x,y)]为什么这个公式成立dis[x]dis[y]相当于把“从根节点到 x 的路”和“从根节点到 y 的路”加了起来。但是从“根节点”到“LCA”的这段路径被重复计算了两次。因此减去 2×dis[LCA] 后剩下的刚好就是 x 到 y 的真实树上路径长度。因此本题的目标被彻底简化为如何在面对 m 次查询时极速求出 LCA(x,y)。二、 算法一倍增法1. 算法设计倍增法的核心思想是二进制拆分。每次往上爬 1 步太慢我们利用动态规划预处理出每个节点往上跳 1,2,4,8…2^j 步到达的祖先。状态定义fa[i][j]表示节点 i 向上跳 2^j 步所到达的祖先节点。状态转移fa[i][j]fa[fa[i][j-1]][j-1]。查询 LCA三步走齐平水位线将深度较大在下面的节点利用 log2​ 代码中使用更快的__lg函数找到最大能跳的 2 的次幂向上跳跃直到与另一个节点深度相同。特判相遇如果此时两点重合说明较浅的点本身就是 LCA。同频逼近两点同时从最大步数开始试探向上跳。如果跳到的祖先不同就放心跳上去如果相同说明跳过头了或者正好是 LCA不跳。循环结束后两人必定停在 LCA 的正下方再往上走 1 步即为答案。2. 时空复杂度时间复杂度* 预处理 DFSO(nlogn)单次查询O(logn)总时间复杂度O((nm)logn)。应对 2×10^4 的数据量绰绰有余。空间复杂度O(nlogn)主要消耗在fa[n][20]数组上。三、 算法二RMQ欧拉序 ST表1. 算法设计面对海量查询倍增的 O(logn) 仍有优化空间。RMQ 算法通过将树形结构降维成一维数组将 LCA 问题转化为静态区间的最值查询问题从而实现单次查询 O(1)。欧拉环游拍扁树沿着树做 DFS不论是“初次到达”还是“从子树回溯”只要经过节点就打卡记录。这样会生成一个长度为 2n−1 的节点访问序列e 表以及对应的深度序列l 表。核心数学性质找到 x 和 y 在欧拉序中第一次出现的位置h[x] 和 h[y]。在欧拉序的区间 [h[x],h[y]] 之间深度最浅即 l 表中值最小的那个节点必定是它们的 LCA。ST 表提速利用ST表算法预处理深度表 l即可在 O(1) 时间内查询出任意区间内深度最小值的下标映射回 e 表得出 LCA。2. 时空复杂度时间复杂度* 预处理 DFS ST表构建O(nlogn)单次查询O(1)总时间复杂度O(nlognm)。查询速度达到理论极限。空间复杂度O(nlogn)。由于欧拉序长度为 2nST 表第一维需开到 2n。四、 核心坑点总结避坑指南在具体实现这两种算法时极其容易踩到以下边界陷阱__lg()的定义域死穴__lg(x)的底层是位扫描指令传入0会导致未定义行为。在倍增法的“齐平水位线”操作时必须确保是大深度减小深度__lg(depth[x]-depth[y])且循环条件严格为depth[x]!depth[y]或。ST表的右边界对齐在构建 ST 表时区间起点为i长度为1j则区间右端点为i (1j)-1。必须保证右端点不超过总长度 2n−1。少减 1 会导致末尾合法数据被截断。欧拉序的数组容量越界欧拉环游包含所有回溯过程最终序列长度是 2n−1。因此保存欧拉序的 e 表、l 表以及 ST 表的第一维度、前向星的边数组必须开到 2×10^4 以上maxn1。头文件遗漏使用swap和__lg函数必须显式包含#include algorithm否则在严格的评测机上直接触发CE。五、 完整题解代码版本一倍增法求 LCA//x y两点之间的最短距离即为x到lca(x,y)的距离y到lca(x,y)的距离 //所以两种方法可以求lca //第一种方法倍增求lca #include iostream #include vector #include cstring//对应memset #include algorithm//对应swap等函数 using namespace std; int n,m; int dis[10010];//dis[i]代表点i到根节点的距离 int depth[10010];//depth[i]代表节点i的深度 根节点深度设置为1 //fa[i][j]代表i节点向上2^j步后所处的节点位置 int fa[10010][20]; int h[10010];//h[u]存储节点u的最后一条边的编号 int vtex[20020];//vtex[i]存储第i条边指向的终点 (无向图开两倍) int nxt[20020];//nxt[i]存储与第i条边同起点的上一条边的编号 int wt[20020];//wt[i]存储第i条边的权重 int idx; //链式前向星存图 void addedge(int u,int v,int w){ vtex[idx]v; nxt[idx]h[u]; wt[idx]w; h[u]idx; } //rt为当前节点 fat为当前节点的父节点 d为父节点到当前节点到距离 void dfs(int rt,int fat,int d){ dis[rt]dis[fat]d;//累加距离 depth[rt]depth[fat]1;//深度父节点深度1 //当前节点向上一步为父节点 fa[rt][0]fat; for(int i1;(1i)depth[rt];i){ fa[rt][i]fa[fa[rt][i-1]][i-1]; } int ph[rt];//获取当前节点的第一条边 //遍历当前节点的所有邻接点 while(p!-1){ if(vtex[p]fat){ //因为是无向图 如果邻接点是父亲 直接跳过 pnxt[p]; continue; } dfs(vtex[p],rt,wt[p]); pnxt[p]; } } //查询节点x y的最近公共祖先 int lca(int x,int y){ //让x是x和y里深度较大的那一个 方便后面计算 if(depth[x]depth[y]) swap(x,y); //然后让x和y到同一层 //让x不断向上跳 直到和y处于同一深度 while(depth[x]!depth[y]){ xfa[x][__lg(depth[x]-depth[y])]; } //如果到同一层后 x等于y 说明y就是x和y的最近公共祖先 if(xy) return y; //如果不等 就让x和y往上跳 如果跳到同一个点就缩小步数重新跳 //最后x和y一定是停在他们的最近公共祖先的正下方 for(int i__lg(depth[x]);i0;i--){ //如果跳2^i步后 两者的祖先不同 说明还没越过lca if(fa[x][i]!fa[y][i]){ xfa[x][i]; yfa[y][i]; } } //最后停留在x和y的最近公共祖先的正下方 return fa[x][0]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; //初始化头指针数组为空 memset(h,-1,sizeof(h)); for(int i1;in;i){ int x,y,k; cinxyk; //双向存边 addedge(x,y,k); addedge(y,x,k); } //dfs遍历预处理出fa数组以及depth(深度数组) //因为是树 所以任意节点都可以做为根节点 //我们假定1号节点为根节点 //根节点没有父节点 设置为0 //根节点到根节点的父节点的距离为0 dfs(1,0,0); //共m次询问 while(m--){ int x,y; cinxy; //x到y的最短距离就是 //x到根节点的距离-lca(x,y)到根节点的距离 //y到根节点的距离-lca(x,y)到根节点的距离 coutdis[x]dis[y]-2*dis[lca(x,y)]\n; } return 0; }版本二RMQ 法欧拉序 ST表求 LCA//第二种方法RMQ求lca #include iostream #include cstring//对应memset #include algorithm//对应swap using namespace std; int n,m; const int maxn10010; //e[i]代表对树进行欧拉环游过程中第i个访问到的节点 int e[maxn1]; //l[i]代表欧拉环游过程中所访问到的节点所处的层数 int l[maxn1]; int h[maxn];//h[i]代表i节点第一次在e表中出现的位置 int cnt;//欧拉环游过程中总共访问了多少个点 int h2[maxn]; int vtex[maxn1]; int nxt[maxn1]; int wt[maxn1]; int idx; //d[i]代表i点到根节点的距离 int d[maxn]; //st[i][j]代表以i为起点 区间长度为2^j的区间内 l深度最小的下标 int st[maxn1][20]; //链式前向星存图 void addedge(int u,int v,int w){ vtex[idx]v; nxt[idx]h2[u]; wt[idx]w; h2[u]idx; } //欧拉环游 rt为当前节点 fa为当前节点父节点 void dfs(int rt,int fa){ //记录访问当前节点 e[cnt]rt; //当前访问节点为上一个访问节点儿子 //所以当前访问节点深度为上一个访问节点深度1 l[cnt]l[cnt-1]1; //rt节点第一次在e表中出现的位置下标是cnt h[rt]cnt; int ph2[rt]; //遍历当前节点的所有邻接点 while(p!-1){ //避免重复访问 if(vtex[p]fa){ pnxt[p]; continue; } //记录节点到根节点的距离 d[vtex[p]]d[rt]wt[p]; dfs(vtex[p],rt); //回溯 再记录一次 e[cnt]rt; //回溯 所以当前访问节点是上一个访问节点父亲 //所以当前访问节点深度是上一个访问节点-1 l[cnt]l[cnt-1]-1; pnxt[p]; } } //生成关于l表的st数组 void pre(){ //以i为起点 区间长度为1的区间内 l最小值的下标就是自己 for(int i1;i2*n-1;i) st[i][0]i; //外层循环 遍历区间长度的指数j for(int j1;1j2*n-1;j){ int tmp1(j-1); //内层循环 遍历起点 确保右端点不越界 for(int i1;i(1j)-12*n-1;i){ if(l[st[i][j-1]]l[st[itmp][j-1]]) st[i][j]st[i][j-1]; else st[i][j]st[itmp][j-1]; } } } //st表查询l[x]和l[y]区间最小值的下标 int query(int x,int y){ //确保y永远是x y中较大的 方便后面计算 if(yx) swap(x,y); int k__lg(y-x1); int tmp1k; if(l[st[x][k]]l[st[y-tmp1][k]]) return st[x][k]; else return st[y-tmp1][k]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; //初始化头指针数组为空 memset(h2,-1,sizeof(h2)); //链式前向星存图 for(int i1;in;i){ int x,y,k; cinxyk; addedge(x,y,k); addedge(y,x,k); } //接下来进行欧拉环游 生成e l h表 //假设1号节点为根节点 从1号节点开始遍历 //根节点没有父节点 所以给个虚拟父节点0 dfs(1,0); //预处理完之后 需要对l表进行处理 //生成关于l表的倍增数组 pre(); //m次询问 while(m--){ int x,y; cinxy; //查询h[x] h[y] 即x和y在e表中第一次出现的位置 //然后e[h[x]],e[h[y]]之间深度最小的点就是lca(x,y) //求出lca(x,y)之后 x到y的最短距离就是 //x到根节点的距离-lca(x,y)到根节点的距离 //y到根节点的距离-lca(x,y)到根节点的距离 //1.h[x]和h[y]找到两点在欧拉序里的首次出现下标 //2.query()返回在这个下标区间内找深度最浅的点的下标 //3.e[]将这个最浅的下标映射回真实的lca节点编号 coutd[x]d[y]-2*d[e[query(h[x],h[y])]]\n; } }