<题目链接>
题目大意：
给你一棵带有边权的树，然后进行q次查询，每次查询输出指定两个节点之间的距离。
解题分析：
本题有多重解决方法，首先，可用最短路轻易求解。若只用LCA解决本题，也有三种常用的做法，具体方法如下：
LCA转RMQ解法：
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
;
int dis[M],dep[M],first[M],pos[M];
];
int cnt;
struct Edge{
int to,w;
};
vector<Edge>G[M];
int Min(int a,int b){ //得到深度更小的节点的序号，即更上层的节点
return dep[a]<dep[b]?a:b;
}
void RMQ_init(int n){ //预处理ST表，得到从[i,i+2^j-1]这个区间深度最小的节点的序号，注意，区间的下标代表遍历到的顺序
;i<=n;i++)
st[i][]=i;
;(<<j)<=n;j++)
;i+(<<j)-<=n;i++)
st[i][j]=Min(st[i][j-],st[i+(<<(j-))][j-]);
}
int RMQ(int l,int r){ //得到指定区间内深度最小的节点的编号,注意这里的l和r指的是按dfs顺序遍历的时间序号
))/log(2.0);
<<k)+][k]);
}
int get_LCA(int a,int b){ //在两点遍历顺序的区间内选择深度最小的节点的下标
return first[a]<first[b]?pos[RMQ(first[a],first[b])]:pos[RMQ(first[b],first[a])];
}
void dfs(int u,int fa,int deep){
dep[cnt]=deep,pos[cnt]=u,first[u]=cnt++; //表示cnt时间遍历到的节点的深度，和cnt时间遍历到的节点的序号，和第一次遍历到u节点的时间
;i<G[u].size();i++){
int v=G[u][i].to;
if(v==fa)continue;
dis[v]=dis[u]+G[u][i].w; //更新子节点距离
dfs(v,u,deep+);
pos[cnt]=u; //在dfs搜索完u的所有子节点后，回溯到u
dep[cnt++]=deep; //u的深度仍然为当前的深度
}
}
int main(){
int T,n,m;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
cnt=;
;i<M;i++)
G[i].clear();
;i<n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
G[a].push_back(Edge{b,c}); //建无向边
G[b].push_back(Edge{a,c});
}
dfs(,-,);
RMQ_init(*n-);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
printf(*dis[get_LCA(a,b)]);
}
}
;
}
在线ST解法可以看这篇博客 >>>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
;
struct node{
int to,w,next;
}e[maxn*];
],n,cnt,head[maxn];
void add(int u,int v,int w){
e[cnt].to=v,e[cnt].w=w;
e[cnt].next=head[u],head[u]=cnt++;
}
void dfs(int u,int pre,int t){
dep[u]=t;//深度
f[u]=pre;//父节点
;i=e[i].next){
int v=e[i].to;
if(v!=pre){
dis[v]=dis[u]+e[i].w;//距离跟的距离
dfs(v,u,t+);
}
}
}
void init()
{
//p[i][j]表示i结点的第2^j祖先
int i,j;
;(<<j)<=n;j++)
;i<=n;i++)
p[i][j]=-;
;i<=n;i++)p[i][]=f[i];
;(<<j)<=n;j++)
;i<=n;i++)
]!=-)
p[i][j]=p[p[i][j-]][j-];//i的第2^j祖先就是i的第2^(j-1)祖先的第2^(j-1)祖先
}
int LCA(int x,int y){
if(dep[x]<dep[y])swap(x,y); //令x为深度更深的节点
int d=dep[x]-dep[y];
;(d>>i)!=;i++)
)x=p[x][i]; //以上的操作是处理较深的节点，使两节点深度一致
if(x==y)return x; //如果深度一致时，两节点相同，那么直接返回即可
;i>=;i--)
if(p[x][i]!=p[y][i]){ //跳2^i步不一样，就跳，否则不跳
x=p[x][i];
y=p[y][i];
}
]; //上述操作做完，两点的LCA都在上一层，所以再走一步即可
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int m,i,a,b,c,ans;
scanf("%d%d",&n,&m);
memset(head,-,sizeof(head));
cnt=;
;i<n;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
dis[]=;
dfs(,-,);//找到各点的深度和各点的父节点以及距离根的距离
init(); //初始各个点的2^j祖先是谁
;i<m;i++){
scanf("%d%d",&a,&b);
ans=dis[a]+dis[b]-*dis[LCA(a,b)];
printf("%d\n",ans);
}
}
;
}
离线Tarjan算法可以看这篇博客 >>> ,还有这篇 >>>
#include<iostream>
#include<cstdio>
#include<cstring>
#define Maxn 40010
#define Maxm 210
using namespace std;
struct edge{
int fr,to,w,lca,next;
}p[Maxn<<],ask[Maxm<<];
int head[Maxn],ah[Maxn];
int tot,tot1;
void addedge(int a,int b,int c){
p[tot].to=b;
p[tot].w=c;
p[tot].next=head[a];
head[a]=tot++;
}
void addedge1(int a,int b){
ask[tot1].fr=a;
ask[tot1].to=b;
ask[tot1].next=ah[a];
ah[a]=tot1++;
}
int fa[Maxn];
int findset(int x){ //寻找根节点
return fa[x]==x?x:(fa[x]=findset(fa[x]));
}
void unionset(int a,int b){ //将a、b的根节点链接
fa[findset(a)]=findset(b);
}
int vis[Maxn];
int anc[Maxn];
int dist[Maxn];
void LCA(int u,int fa){
;i=p[i].next){
int v=p[i].to;
if(fa!=v){
dist[v]=dist[u]+p[i].w;
LCA(v,u);
unionset(u,v); //将子树合并到父亲
anc[findset(u)]=u; //维护新集合指向父亲
}
}
vis[u]=; //设置已访问
;i=ask[i].next){ //处理与u关联的边
int v=ask[i].to;
if(vis[v]) //若v已访问,则说明u,v的lca是v所在集合的指向
ask[i].lca=ask[i^].lca=anc[findset(v)];
}
}
void init(int n){
tot=tot1=;
memset(head,-,sizeof head);
memset(ah,-,sizeof ah);
memset(vis,,sizeof vis);
;i<=n;i++) fa[i]=i;
}
int main()
{
int t,n,m,a,b,c;
cin>>t;
while(t--){
cin>>n>>m;
init(n);
;i<n;i++){
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
;i<=m;i++){ //把全部的query也建一颗无向树，进行离线处理
scanf("%d%d",&a,&b);
addedge1(a,b);
addedge1(b,a);
}
dist[]=;
LCA(,-);
;i<tot1;i+=)
printf(*dist[ask[i].lca]);
}
;
}
2018-10-20