cogs 2450. 距离 树链剖分求LCA最近公共祖先 快速求树上两点距离 详细讲解 带注释!

在一个村子里有N个房子,一些双向的路连接着他们。人们总喜欢问这个“如果1想从房子A走到房子B有多远?”这个通常很难回答。但幸运的是在这个村里答案总是唯一的,自从道路修建以来这只有唯一的一条路(意思是你不能去一个地方两次)在每两座房子之间。你的工作是回答所有好奇的人。

【输入格式】

 

输入文件第一行有两个数n(2≤n≤10000)和m(1≤m≤20000),即房子数和问题数。后面n-1行每行由3个数构成i,j,k,由空格隔开,意思是房子i和房子j之间距离为k(0<k≤100)。房子以1到n标记。

下面m行每行有两个不同的整数i和j,你需要回答房子i和房子j之间的距离

 

【输出格式】

输出有n行。每行表示个一个问题的答案。

【样例1】 输入样例1: 3 2 1 2 10 3 1 15 1 2 2 3 输出样例1: 10 25 【样例2】 输入样例2: 2 2 1 2 100 1 2 2 1 输出样例2: 100 100 【提示】

在此键入。

【来源】

在此键入。

 

 

本人决定:认真细致地讲一下树链剖分求LCA  以及速地求树上两点的距离的方法

 

首先来讲解一下树链剖分的模板

1.首先要读入边 建边

cogs 2450. 距离 树链剖分求LCA最近公共祖先 快速求树上两点距离 详细讲解 带注释!

根据具体的题目来决定是要建单向边还是双向边

2.两个dfs来进行树链剖分的预处理

cogs 2450. 距离 树链剖分求LCA最近公共祖先 快速求树上两点距离 详细讲解 带注释!

cogs 2450. 距离 树链剖分求LCA最近公共祖先 快速求树上两点距离 详细讲解 带注释!

3.写一下lca函数

cogs 2450. 距离 树链剖分求LCA最近公共祖先 快速求树上两点距离 详细讲解 带注释!

4.询问+输出答案

cogs 2450. 距离 树链剖分求LCA最近公共祖先 快速求树上两点距离 详细讲解 带注释!

这是一个非常巧妙的处理

cogs 2450. 距离 树链剖分求LCA最近公共祖先 快速求树上两点距离 详细讲解 带注释!

可以从上面的这一个图看出x到Root的距离 - lca到Root的距离  =  x到lca的距离     

              y到Root的距离   -   lca到Root的距离  =  y到lca的距离     

两式合并得dis[x]  -  dis[lca]   +dis[y]  -  dis[lca]   =   x到y的距离

    得出公式 dis[x]+dis[y]-2*dis[lca(x,y)]  =  x到y的距离

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwsspz.html