【LCA模版】

love

[C++] syntaxhighlighter_viewsource syntaxhighlighter_copycode

#include<cstdio>
#include<cmath>
using namespace std;
int n,m,cnt;
int End[5005],Last[5005],Next[5005],Len[5005],F[5005][20],D[5005],Sum[5005][20];
void add(int x,int y,int z){
	End[++cnt]=y;
	Next[cnt]=Last[x];
	Last[x]=cnt;
	Len[cnt]=z;
}
void DFS(int x){
	D[x]=D[F[x][0]]+1;
	for(int i=1;i<=ceil(log2(D[x]));i++)F[x][i]=F[F[x][i-1]][i-1],Sum[x][i]=Sum[x][i-1]+Sum[F[x][i-1]][i-1];
	for(int i=Last[x];i;i=Next[i]){
		if(End[i]==F[x][0])continue;
		F[End[i]][0]=x;Sum[End[i]][0]=Len[i];
		DFS(End[i]);
	}
}
int LCA(int x,int y){
	if(D[x]<D[y])swap(x,y);
	int k=D[x]-D[y],tot=0;
	for(int i=0;i<=ceil(log2(k));i++)if((1<<i)&k)tot+=Sum[x][i],x=F[x][i];
	if(x==y)return tot;
	k=D[x];
	for(int i=ceil(log2(k));i>=0;i--)if(F[x][i]!=F[y][i])tot+=(Sum[x][i]+Sum[y][i]),x=F[x][i],y=F[y][i];
	return tot+Sum[x][0]+Sum[y][0];
}
int main(){
	int a,b,c;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);add(b,a,c);
	}
	DFS(1);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		printf("%d\n",LCA(a,b));
	}
}