这是一个很裸的LCA。
觉得hzwer的LCA模版更加优美，于是膜拜了一下。
#include<cstdio>
#include<algorithm>
using namespace std;
int fa[1005][12],f[1005],n,q,en,h[1005],deep[1005],flg[1005];
struct Edge{
int b,v,next;
}e[2005];
void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
void Yuchuli(int u){
flg[u]=1;
for(int i=1;i<=10;i++){
if(deep[u]<(1<<i))break;
fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(flg[v])continue;
f[v]=f[u]+e[i].v;
fa[v][0]=u;
deep[v]=deep[u]+1;
Yuchuli(v);
}
}
int LCA(int u,int v){
if(deep[u]<deep[v])swap(u,v);
int dep=deep[u]-deep[v];
for(int i=0;i<=10;i++)if((1<<i)&dep)u=fa[u][i];
for(int i=10;i>=0;i--){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i];
v=fa[v][i];
}
}
return u==v?u:fa[u][0];
}
int main(){
freopen("1602.in","r",stdin);
freopen("1602.out","w",stdout);
scanf("%d %d",&n,&q);
for(int i=1;i<n;i++){
int sa,sb,sc;
scanf("%d %d %d",&sa,&sb,&sc);
add(sa,sb,sc);
add(sb,sa,sc);
}
Yuchuli(1);
while(q--){
int sa,sb;
scanf("%d %d",&sa,&sb);
printf("%d\n",f[sa]+f[sb]-2*f[LCA(sa,sb)]);
}
return 0;
}
评论 (0)
