题意:求树上两点的最短距离。考查lca,预处理点到根的距离dist,则两点a、b之间的最短距离是dist[a]+dist[b]-2*dist[p];p是a、b最近公共祖先。
关于lcahttps://blog.csdn.net/my_sunshine26/article/details/72717112
#include<bits/stdc++.h> using namespace std; const int N = 10005; const int M = 2*N; int e[M],ne[M],w[M],h[M]; int dist[N]; int res[N]; int st[N]; int f[N]; int idx; vector<pair<int,int >>q[M]; int find(int a){ if(f[a]!=a)f[a]=find(f[a]); return f[a]; } void add(int a,int b,int v){ e[idx]=b;ne[idx]=h[a];w[idx]=v;h[a]=idx++; } void dfs(int u,int f){ for(int i=h[u];~i;i=ne[i]){ int j=e[i]; if(j!=f){ dist[j]=dist[u]+w[i]; dfs(j,u); } } } void tarjan(int u){ st[u]=1; for(int i=h[u];~i;i=ne[i]){ int j=e[i]; if(!st[j]){ tarjan(j); f[j]=u; } } for(int i=0;i<q[u].size();i++){ int to=q[u][i].first; int pos=q[u][i].second; int anc=find(u); if(st[to]==2){ res[pos]=dist[u]+dist[to]-2*dist[anc]; } } st[u]=2; } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)f[i]=i; memset(h,-1,sizeof(h)); for(int i=1;i<n;i++){ int a,b,v; scanf("%d%d%d",&a,&b,&v); add(a,b,v); add(b,a,v); } for(int i=0;i<m;i++){ int x,y; scanf("%d%d",&x,&y); q[x].push_back(make_pair(y,i)); q[y].push_back(make_pair(x,i)); } dfs(1,-1); tarjan(1); for(int i=0;i<m;i++){ printf("%d\n",res[i]); } return 0; }