文章来源地址https://www.toymoban.com/news/detail-630881.html
输入样例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#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,x,y,k,res[N];
int vis[N];
int dis[N];
int p[N];
vector<pair<int,int>>query[N],e[N];
void dfs(int u,int fa){
for(auto it:e[u]){
int to=it.first;
if(to==fa) continue;
dis[to]=dis[u]+it.second;
dfs(to,u);
}
}
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
void tarjan(int u){
vis[u]=1;
for(auto it:e[u]){
int to=it.first;
if(!vis[to]){
tarjan(to);
p[to]=u;
}
}
for(auto it:query[u]){
int y=it.first;
int id=it.second;
if(vis[y]==2){
int anc=find(y);
res[id]=dis[u]+dis[y]-dis[anc]*2;
}
}
vis[u]=2;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n-1;i++){
scanf("%d%d%d",&x,&y,&k);
e[x].push_back({y,k});
e[y].push_back({x,k});
}
for(int i=0;i<m;i++){
scanf("%d%d",&x,&y);
if(x!=y){
query[x].push_back({y,i});
query[y].push_back({x,i});
}
}
for(int i=1;i<=n;i++) p[i]=i;
dfs(1,-1);
tarjan(1);
for(int i=0;i<m;i++) printf("%d\n",res[i]);
return 0;
}文章来源：https://www.toymoban.com/news/detail-630881.html
到了这里，关于AcWing1171. 距离（lca&&tarjan）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
