题目描述
给出 n 个点的一棵树,多次询问两点之间的最短距离。
注意:边是双向的。
输入格式
第一行为两个整数 n 和 m。n 表示点数,m 表示询问次数;
下来 n-1 行,每行三个整数 x ,y, k,表示点 x 和点 y 之间存在一条边长度为 k;
再接下来 m 行,每行两个整数 x,y,表示询问点 x 到点 y 的最短距离。
输出格式
输出 m 行。对于每次询问,输出一行。
样例 1
Input
2 2
1 2 100
1 2
2 1
Output
100
100
样例 2
Input Output
3 2
1 2 10
3 1 15
1 2
3 2
Output
10
25
数据范围与提示
对于全部数据,2<=n<=10 ^ 4,1<=m<= 2* 10^4,0< k<= 100,1<=x,y<= n.
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int dis[N],father[N],tot,head[N],dep[N],f[N][21];
int n,m,s;
struct node {
int next,to,dis;
} p[N<<1];
void add(int a,int b,int len) {
p[++tot].to=b;
p[tot].next=head[a];
p[tot].dis=len;
head[a]=tot;
}
void dfs(int u,int fa) {
f[u][0]=fa;
for(int i=1; (1<<i)<=dep[u]; ++i)
f[u][i]=f[f[u][i-1]][i-1];
for(int i=head[u]; i; i=p[i].next) {
if(p[i].to==fa) continue;
dep[p[i].to]=dep[u]+1;
dis[p[i].to]=dis[u]+p[i].dis;
dfs(p[i].to,u);
}
}
int lca(int x,int y) {
if(dep[x]>dep[y]) swap(x,y);
for(int i=20; i>=0; --i)
if(dep[x]<=dep[y]-(1<<i))
y=f[y][i];
if(x==y) return x;
for(int i=20; i>=0; --i) {
if(f[x][i]==f[y][i]) continue;
x=f[x][i];
y=f[y][i];
}
return f[x][0];
}
int main() {
cin>>n>>m;
for(int i=1; i<=n-1; ++i) {
int x,y,l;
cin>>x>>y>>l;
add(x,y,l);
add(y,x,l);
}
dfs(1,0);
for(int i=1; i<=m; ++i) {
int x,y;
cin>>x>>y;
cout<<dis[x]+dis[y]-2*dis[lca(x,y)]<<endl;
}
return 0;
}