题意:求树上两点的最短距离。考查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];//first是另一个点，second是编号 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; if(st[to]==2){//如果已经标记过且被回溯过，证明其当前祖先已确定 int anc=find(to);//该点的当前记录的根节点即是两点的最近公共祖先 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 ",res[i]); } return 0; }