两道lca模板题，用的是倍增法，nlogn预处理，logn查询。
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; #define maxn 10100 struct Edge { int u,v,w,next; }e[100100]; int n,m,c; int head[maxn],cnt; int fa[maxn],cost[maxn],L[maxn]; int anc[maxn][20]; int parent[maxn]; int find(int x) { if(parent[x]==x) return x; else return parent[x]=find(parent[x]); } void add(int u,int v,int w) { e[cnt].u=u; e[cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u,int father,int level) { int i; L[u]=level; for(i=head[u];i!=-1;i=e[i].next) { int v=e[i].v; if(v!=father) { fa[v]=u; cost[v]=cost[u]+e[i].w; dfs(v,u,level+1); } } } void pre() { int i,j; for(i=0;i<n;i++) { anc[i][0]=fa[i]; for(j=1;(1<<j)<n;j++) anc[i][j]=-1; } for(j=1;(1<<j)<n;j++) for(i=0;i<n;i++) { if(anc[i][j-1]!=-1) { int a=anc[i][j-1]; anc[i][j]=anc[a][j-1]; } } } int query(int p,int q) { int tmp,log,i; if(L[p]<L[q]) swap(p, q); for(log=1;(1<<log)<=L[p];log++);log--; int ans=-1000000000; for(i=log;i>=0;i--) if(L[p]-(1<<i)>=L[q]) p=anc[p][i]; if(p==q) return p; for(i=log;i>=0;i--) { if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]) { p=anc[p][i]; q=anc[q][i]; } } return fa[p]; } int main() { int i,j; while(scanf("%d%d%d",&n,&m,&c)!=EOF) { memset(head,-1,sizeof(head)); cnt=0; int x,y,z; for(i=1;i<=n;i++) parent[i]=i; for(i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); int px=find(x); int py=find(y); if(px!=py) parent[px]=py; } for(i=1;i<=n;i++) if(parent[i]==i) { add(0,i,0); add(i,0,0); } n++; cost[0]=0; dfs(0,-1,0); pre(); for(i=1;i<=c;i++) { scanf("%d%d",&x,&y); if(find(x)!=find(y)) printf("Not connected "); else { int xx=query(x,y); printf("%d ",cost[x]+cost[y]-2*cost[xx]); } } } return 0; }
#pragma comment(linker, "/STACK:1000000000,1000000000") #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; #define maxn 40100 struct Edge { int u,v,w,next; }e[100100]; int n,m; int head[maxn],cnt; int fa[maxn],cost[maxn],L[maxn]; int anc[maxn][20]; void add(int u,int v,int w) { e[cnt].u=u; e[cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt++; } void dfs(int u,int father,int level) { int i; L[u]=level; for(i=head[u];i!=-1;i=e[i].next) { int v=e[i].v; if(v!=father) { fa[v]=u; cost[v]=cost[u]+e[i].w; dfs(v,u,level+1); } } } void pre() { int i,j; for(i=0;i<n;i++) { anc[i][0]=fa[i]; for(j=1;(1<<j)<n;j++) anc[i][j]=-1; } for(j=1;(1<<j)<n;j++) for(i=0;i<n;i++) { if(anc[i][j-1]!=-1) { int a=anc[i][j-1]; anc[i][j]=anc[a][j-1]; } } } int query(int p,int q) { int tmp,log,i; if(L[p]<L[q]) swap(p, q); for(log=1;(1<<log)<=L[p];log++);log--; int ans=-1000000000; for(i=log;i>=0;i--) if(L[p]-(1<<i)>=L[q]) p=anc[p][i]; if(p==q) return p; for(i=log;i>=0;i--) { if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]) { p=anc[p][i]; q=anc[q][i]; } } return fa[p]; } int main() { int cas,i,j; scanf("%d",&cas); while(cas--) { scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); cnt=0; int x,y,z; for(i=1;i<n;i++) { scanf("%d%d%d",&x,&y,&z); x--; y--; add(x,y,z); add(y,x,z); } dfs(0,-1,0); pre(); cost[0]=0; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); x--;y--; int xx=query(x,y); printf("%d ",cost[x]+cost[y]-2*cost[xx]); } } return 0; }