首页 > 代码库 > hdu 2586 树上点对最近距离 （lca）
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）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。