[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]=F[F[x][i-1]][i-1],Sum[x]=Sum[x][i-1]+Sum[F[x][i-1]][i-1];
for(int i=Last[x];i;i=Next){
if(End==F[x][0])continue;
F[End][0]=x;Sum[End][0]=Len;
DFS(End);
}
}
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],x=F[x];
if(x==y)return tot;
k=D[x];
for(int i=ceil(log2(k));i>=0;i--)if(F[x]!=F[y])tot+=(Sum[x]+Sum[y]),x=F[x],y=F[y];
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));
}
}