1171.距离（蓝桥真题）
样例1输入：
2 2
1 2 100
1 2
2 1样例1输出：
100
100样例2输入：
3 2
1 2 10
3 1 15
1 2
3 2样例2输出：
10
25分析：如果要是每次询问的是两个点之间的最近公共祖先那么这道题就是lca板子了，但是他问的是最短距离，那么就需要在lca板子的基础上稍加改变，不懂lca的小伙伴可以看下这里：最近公共祖先（LCA）（树上倍增）_lca树上倍增_AC__dream的博客-CSDN博客
其实改变的也很简单，就是加上一个dis数组，dis[x][i]代表x的第2^i个祖先节点到x节点的距离，然后我们在x和y寻找最近共同祖先的过程中统计一下两者的距离就可以，至于dis数组的更新和f数组的更新是一样的。
细节见代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],h[N],w[N],idx;
int f[N][21],d[N],dis[N][21];
//d[i]表示当前节点所在的深度
void add(int x,int y,int z)
{e[idx]=y;w[idx]=z;ne[idx]=h[x];h[x]=idx++;
}
void dfs(int x,int fa,int distance)//distance代表节点x和fa的距离
{d[x]=d[fa]+1;f[x][0]=fa;dis[x][0]=distance;for(int i=1;i<=20;i++){f[x][i]=f[f[x][i-1]][i-1];dis[x][i]=dis[x][i-1]+dis[f[x][i-1]][i-1];}for(int i=h[x];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;dfs(j,x,w[i]);}return ;
}
int lca(int x,int y)
{if(d[x]<d[y]) swap(x,y);int ans=0;for(int i=20;i>=0;i--)if(d[f[x][i]]>=d[y]){ans+=dis[x][i];x=f[x][i];}if(x==y) return ans;for(int i=20;i>=0;i--)if(f[x][i]!=f[y][i]){ans+=dis[x][i]+dis[y][i];x=f[x][i];y=f[y][i];}ans+=dis[x][0]+dis[y][0];return ans;
}
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)h[i]=-1;for(int i=1;i<n;i++){int u,v,z;scanf("%d%d%d",&u,&v,&z);add(u,v,z);add(v,u,z);}dfs(1,0,0);while(m--){int u,v;scanf("%d%d",&u,&v);printf("%d\\n",lca(u,v));}return 0;
}