【LCA模版】
本帖最后由 李维强-15级 于 2018-6-15 01:40 编辑#include<cstdio>
#include<cmath>
using namespace std;
int n,m,cnt;
int End,Last,Next,Len,F,D,Sum;
void add(int x,int y,int z){
End[++cnt]=y;
Next=Last;
Last=cnt;
Len=z;
}
void DFS(int x){
D=D]+1;
for(int i=1;i<=ceil(log2(D));i++)F=F],Sum=Sum+Sum];
for(int i=Last;i;i=Next){
if(End==F)continue;
F]=x;Sum]=Len;
DFS(End);
}
}
int LCA(int x,int y){
if(D<D)swap(x,y);
int k=D-D,tot=0;
for(int i=0;i<=ceil(log2(k));i++)if((1<<i)&k)tot+=Sum,x=F;
if(x==y)return tot;
k=D;
for(int i=ceil(log2(k));i>=0;i--)if(F!=F)tot+=(Sum+Sum),x=F,y=F;
return tot+Sum+Sum;
}
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));
}
}
页:
[1]