lca上的tarjan，改了我一下午加一晚上的bug，还无奈重写了一次。就是寻找最近公共祖先lca（u，v
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=40000+100; int n,m,k1,k2,t; int hade1[maxn],hade2[maxn]; int d[maxn],c[maxn]; bool vis[maxn]; struct note { int fr; int next; int to; int len; int lca; }aa[maxn*2],bb[1000]; void addage1(int fr,int to,int len) { aa[k1].to=to; aa[k1].len=len; aa[k1].next=hade1[fr]; hade1[fr]=k1++; } void addage2(int fr,int to) { bb[k2].fr=fr; bb[k2].to=to; bb[k2].lca=-1; bb[k2].next=hade2[fr]; hade2[fr]=k2++; } void init() { memset(hade1,-1,sizeof(hade1)); memset(hade2,-1,sizeof(hade2)); memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); k1=k2=0; } int found(int x) { if(x==c[x]) return x; else return c[x]=found(c[x]); } void unit(int x,int y) { x=found(x); y=found(y); if(x!=y) c[y]=x; } void tarjan(int u) { vis[u]=1; c[u]=u; for(int i=hade1[u];i!=-1;i=aa[i].next) { int v=aa[i].to; int w=aa[i].len; if(!vis[v]) { d[v]=d[u]+w;//从此节点到根节点的距离 tarjan(v); unit(u,v); } } for(int i=hade2[u];i!=-1;i=bb[i].next) { int v=bb[i].to; if(vis[v]) { bb[i].lca=bb[i^1].lca=found(v);//回溯的是u和v最近公共子节点的分支，所以v是指向最近公共子节点的 } } } int main() { scanf("%d",&t); while(t--) { init(); scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { int fr,to,len; scanf("%d%d%d",&fr,&to,&len); addage1(fr,to,len); addage1(to,fr,len); } for(int i=0;i<m;i++) { int fr,to; scanf("%d%d",&fr,&to); addage2(fr,to); addage2(to,fr); } d[1]=0; tarjan(1); for(int i=0;i<m;i++) { int s=i*2; int u=bb[s].fr,v=bb[s].to,lca=bb[s].lca; int mm=d[u]+d[v]-2*d[lca]; printf("%d\n",mm); } } return 0; }
）
转载于:https://www.cnblogs.com/Wangwanxiang/p/7524545.html
相关资源：数据结构—成绩单生成器