【模板】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 ;
 }