LCA tarjan算法模板题
题意：给一个无根树，有q个询问，，每个询问两个点，问两点的距离。
用tarjan离线算法算出每个询问的两点的最近公共祖先
ans[i]=dis[x[i]]+dis[y[i]]-2*dis[z[i]]; // x[i],y[i]分别存储每次询问的两点，z[i]存储这两点的最近公共祖先
#include "stdio.h"#include "string.h"int tot,n,m;int f[40010],x[40010],y[40010],z[40010],dis[40010],vis[40010],head[40010];struct node{int to,next,v;}edge[80010];void add_edge(int a,int b,int c){edge[tot].to=b;edge[tot].next=head[a];edge[tot].v=c;head[a]=tot++;}int fin(int x){if (f[x]!=x)return f[x]=fin(f[x]);return f[x];}void tarjan(int w){int i;vis[w]=1;f[w]=w;for (i=1;i<=m;i++){if (vis[y[i]] && x[i]==w) z[i]=fin(y[i]);if (vis[x[i]] && y[i]==w) z[i]=fin(x[i]);}for (i=head[w];i!=-1;i=edge[i].next)if (vis[edge[i].to]==0){dis[edge[i].to]=dis[w]+edge[i].v;tarjan(edge[i].to);f[edge[i].to]=w;}}int main(){int t,a,b,c,i;scanf("%d",&t);while (t–){scanf("%d%d",&n,&m);tot=0;memset(head,-1,sizeof(head));for (i=1;i<n;i++){scanf("%d%d%d",&a,&b,&c);add_edge(a,b,c);add_edge(b,a,c);}memset(z,0,sizeof(z));memset(x,0,sizeof(x));memset(y,0,sizeof(y));for (i=1;i<=m;i++)scanf("%d%d",&x[i],&y[i]);dis[1]=0;memset(vis,0,sizeof(vis));tarjan(1);for (i=1;i<=m;i++)printf("%d\n",dis[x[i]]+dis[y[i]]-2*dis[z[i]]);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
在人生的道路上，谁都会遇到困难和挫折，
