本文主要是介绍hdu 2586 树上点对最近距离 （lca），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
,只要知道dis[i][j]=dis[i][root]+dis[j][root]-2*dis[Lca(i,j)][root]. 其中root为树的根节点，LCA(i,j)为i,j的最近公共祖先。 所以我们先把所有的询问储存下来，然后离线直接查询。复杂度是o(n+q)的。
VIE
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<stdlib.h>
using namespace std;
const int mmax= 40010;
const int mod=1000000007;
typedef long long LL;struct node
{int en,len;int next;
}E[2*mmax];
int p[mmax],num;
void init()
{memset(p,-1,sizeof p);num=0;
}
void add(int st,int en,int len)
{E[num].en=en;E[num].len=len;E[num].next=p[st];p[st]=num++;
}
struct nodes
{int v;int next;
}Q[mmax];
int Qp[mmax];
int Qnum;
void initQ()
{memset(Qp,-1,sizeof Qp);Qnum=0;
}
void addQ(int u,int v )
{Q[Qnum].v=v;Q[Qnum].next=Qp[u];Qp[u]=Qnum++;
}
int dis[mmax],fa[mmax],ans[mmax];
bool vis[mmax];
int find(int x)
{if(x==fa[x])return x;return fa[x]=find(fa[x]);
}
void Lca(int u)
{vis[u]=1;for(int i=Qp[u];i+1;i=Q[i].next){int v=Q[i].v;if(vis[v])ans[i/2]=dis[u]+dis[v]-2*dis[find(v)];}for(int i=p[u];i+1;i=E[i].next){int v=E[i].en;if(!vis[v]){dis[v]=dis[u]+E[i].len;Lca(v);fa[v]=u;}}
}
int main()
{int t,n,m;int u,v,len;cin>>t;while(t--){init();initQ();scanf("%d %d",&n,&m);for(int i=0;i<=n;i++)fa[i]=i;for(int i=1;i<n;i++){scanf("%d %d %d",&u,&v,&len);add(u,v,len);add(v,u,len);}for(int i=0;i<m;i++){scanf("%d %d",&u,&v);addQ(u,v);addQ(v,u);}memset(vis,0,sizeof vis);dis[1]=0;Lca(1);for(int i=0;i<m;i++)printf("%d\n",ans[i]);}return 0;
}
W CODE
这篇关于hdu 2586 树上点对最近距离 （lca）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
