【模板】Lca倍增法

Codevs 1036 商务旅行

 #include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m,x,y,ans=,tot=,last[maxn],dep[maxn],p[maxn][];
struct edge{
int to,pre;
}e[maxn<<]; void read(int &k){
k=; int f=; char c=getchar();
while (c<''||c>'')c=='-'&&(f=-),c=getchar();
while (''<=c&&c<='')k=k*+c-'',c=getchar();
k*=f;
}
void add(int x,int y){
e[++tot].to=y;
e[tot].pre=last[x];
last[x]=tot;
}
void dfs(int u,int fa){
dep[u]=dep[fa]+; p[u][]=fa;
for (int i=;i<=log2(dep[u]);i++) p[u][i]=p[p[u][i-]][i-];
for (int i=last[u],to=e[i].to;i;i=e[i].pre,to=e[i].to)
if (to!=fa) dfs(to,u);
}
int lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);
if (dep[x]>dep[y])
for (int i=log2(dep[x]-dep[y]+);i>=,dep[x]!=dep[y];i--)
if (dep[p[x][i]]>=dep[y]) x=p[x][i];
if (x==y) return x;
for (int i=log2(dep[x]);i>=;i--)
if (p[x][i]!=p[y][i]) x=p[x][i],y=p[y][i];
return p[x][];
}
int main(){
read(n);
for (int i=;i<n;i++){
read(x); read(y);
add(x,y); add(y,x);
}
dfs(,);
read(m); read(x);
for (int i=;i<m;i++){
read(y);
ans+=dep[x]+dep[y]-(dep[lca(x,y)]<<);
x=y;
}
printf("%d\n",ans);
return ;
}
上一篇:LCA - 倍增法去求第几个节点


下一篇:luogu3379 【模板】最近公共祖先(LCA) 倍增法