LCA || BZOJ 1602: [Usaco2008 Oct]牧场行走 || Luogu P2912 [USACO08OCT]牧场散步Pasture Walking

题面:[USACO08OCT]牧场散步Pasture Walking

题解:LCA模版题

代码:

 #include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=,max_log=;
int N,Q,F[maxn+][max_log+],edge_head[maxn+],num_edge=,c,Dep[maxn+],u,v,w,A,B;
int Sig[maxn+];
struct Edge{
int to,nx,dis;
}edge[(maxn<<)+];
inline void Add_edge(int from,int to,int dis){
edge[++num_edge].nx=edge_head[from];
edge[num_edge].to=to;
edge[num_edge].dis=dis;
edge_head[from]=num_edge;
return;
}
inline void Dfs(int x,int fa){
Dep[x]=Dep[fa]+;
F[x][]=fa;
for(int i=;i<=max_log;i++)
F[x][i]=F[F[x][i-]][i-];
for(int i=edge_head[x];i;i=edge[i].nx){
int y=edge[i].to;
if(y==fa)continue;
Sig[y]=Sig[x]+edge[i].dis;
Dfs(y,x);
}
return;
}
inline int LCA(int x,int y){
if(Dep[x]<Dep[y]){
int t=x;x=y;y=t;
}
for(int i=max_log;i>=;i--){
int a;a=F[x][i];
if(Dep[a]>=Dep[y])x=a;
if(x==y)return x;
}
for(int i=max_log;i>=;i--){
int a,b;a=F[x][i];b=F[y][i];
if(a!=b){
x=a;y=b;
}
}
return F[x][];
}
int main(){
scanf("%d%d",&N,&Q);
for(int i=;i<N;i++){
scanf("%d%d%d",&u,&v,&w);
Add_edge(u,v,w);
Add_edge(v,u,w);
}
Dfs(,);
while(Q--){
scanf("%d%d",&A,&B);
c=LCA(A,B);
printf("%d\n",Sig[A]+Sig[B]-Sig[c]-Sig[c]);
}
return ;
}

By:AlenaNuna

上一篇:洛谷 题解 P1284 【三角形牧场】


下一篇:BZOJ1012 [JSOI2008]最大数 线段树