首页 > 代码库 > hdu 2586 How far away? （LCA模板）
hdu 2586 How far away? （LCA模板）
题意：
N个点，形成一棵树，边有长度。
M个询问，每个询问(a,b)，询问a和b的距离
思路：
模板题，看代码。DFS预处理算出每个结点离根结点的距离。
注意：
qhead[maxn]，而不是qhead[maxm]。
输出用%I64d，不要用%lld。
C++ RE后 尝试用 G++交。
代码：
struct node{ int to,w,next,lca;};int const maxn = 40005;int const maxm = 205;int fa[maxn];int head[maxn], qhead[maxn];int cnt1,cnt2;ll d[maxn];ll res[maxm*2];bool vis[maxn];node edge[2*maxn];node qedge[2*maxm];int n,m;int findFa(int x){ return fa[x]==x?x:fa[x]=findFa(fa[x]);}inline void Addedge(int u,int v,int w){ edge[++cnt1].w=w, edge[cnt1].to=v, edge[cnt1].next=head[u], head[u]=cnt1; edge[++cnt1].w=w, edge[cnt1].to=u, edge[cnt1].next=head[v], head[v]=cnt1;}inline void Addqedge(int u,int v){ qedge[++cnt2].to=v, qedge[cnt2].next=qhead[u], qhead[u]=cnt2; qedge[++cnt2].to=u, qedge[cnt2].next=qhead[v], qhead[v]=cnt2;}void dfs(int u,int fa,ll w){ d[u]=w; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==fa) continue; dfs(v,u,w+edge[i].w); }}void Tarjan_LCA(int u){ fa[u]=u, vis[u]=true; for(int i=head[u];i!=-1;i=edge[i].next){ if(!vis[edge[i].to]){ //防止访问到父亲 Tarjan_LCA(edge[i].to); fa[edge[i].to]=u; } } for(int i=qhead[u];i!=-1;i=qedge[i].next){ if(vis[qedge[i].to]){ qedge[i].lca=findFa(qedge[i].to); res[i]=d[u]+d[qedge[i].to]-2*d[qedge[i].lca]; } }}void init(){ rep(i,1,n) fa[i]=i; mem(head,-1); mem(qhead,-1); mem(vis,false); mem(d,0); mem(res,0); cnt1=cnt2=0;}int T,a,b,w;int main(){ cin>>T; while(T--){ scanf("%d%d",&n,&m); init(); rep(i,1,n-1){ scanf("%d%d%d",&a,&b,&w);; Addedge(a,b,w); } rep(i,1,m){ scanf("%d%d",&a,&b); Addqedge(a,b); } dfs(1,-1,0); Tarjan_LCA(1); for(int i=1;i<=cnt2;i+=2){ if(res[i]) printf("%I64d\n",res[i]); else printf("%I64d\n",res[i+1]); } }}
hdu 2586 How far away? （LCA模板）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。