happytug wordpressseo自学网站

题目描述
给出 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
对于全部数据，2≤$n$≤$10^4$,1≤$m$≤$2\times 10^4$,0<$k$≤$100$,1≤$x,y$≤$n$
首先这道题肯定是不能直接暴力跑的
但是换一个角度想，这是一棵树，先画个图：

比如说我们要求3到4的距离：
1，我们先找出3和4的公共祖先——2
2，把3的深度与4的深度加起来
3，减去重复的部分（根节点到最近公共祖先）

求任意两点的距离大概就是这个思路
然后来看一个重要的数组——$f$数组
$f[i]$表示的是节点$i$的祖先节点
$find()$函数的作用就是找到祖先节点
后面就是dfs遍历节点同时找最近公共祖先

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5;
struct node{int to,dis;
};
vector<node>a[N];
struct nod{int to,num;
};
vector<nod>q[N];
int n,m;
int vis[N],dis[N],res[N],f[N];
int find(int x){//找祖先函数if(f[x]!=x)f[x]=find(f[x]);return f[x];
}
void dfs(int x){vis[x]=1;for(int i=0;i<a[x].size();i++){//最近的公共祖先肯定要是最短路int v=a[x][i].to;int w=a[x][i].dis;if(vis[v]==0){dis[v]=dis[x]+w;dfs(v);f[v]=x;}}for(int i=0;i<q[x].size();i++){int to=q[x][i].to;int num=q[x][i].num;if(vis[to]==2){res[num]=dis[x]+dis[to]-2*dis[find(to)];//计算距离}}vis[x]=2;
}
signed main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);a[u].push_back(node{v,w});a[v].push_back(node{u,w});}for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);q[x].push_back(nod{y,i});q[y].push_back(nod{x,i});}dfs(1);for(int i=1;i<=m;i++)printf("%d\n",res[i]);//离线输出
}

最后，祝程序员们节日快乐









……祝方昳杨生日快乐……
还有……
对不起……