P8855 [POI2002] 商务旅行

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e4+5;
int n,m,ans,deep[maxn],Log2[maxn],fa[maxn][20];
vector<int>to[maxn];
void init(){
    for(int i=2;i<=n;i++){
        Log2[i]=Log2[i>>1]+1;
    }
}
void dfs(int u,int ff){
    fa[u][0]=ff;
    deep[u]=deep[ff]+1;
    for(int i=1;i<=Log2[deep[u]];i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    int len=to[u].size();
    for(int i=0,v;i<len;i++){
        v=to[u][i];
        if(v==ff){
            continue;
        }
        dfs(v,u);
    }
}
int lca(int u,int v){
    if(deep[u]<deep[v]){
        swap(u,v);
    }
    int tmp=deep[u]-deep[v];
    int ans=tmp;
    for(int i=Log2[tmp];i>=0;i--){
        if((tmp>>i)&1){
            u=fa[u][i];
        }
    }
    if(u==v){
        return ans;
    }
    for(int i=Log2[deep[u]];i>=0;i--){
        if(fa[u][i]^fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
            ans+=(1<<i)<<1;
        }
    }
    ans+=2;
    return ans;
}
int main(){
    scanf("%d",&n);
    init();
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        to[u].push_back(v);
        to[v].push_back(u);
    }
    dfs(1,0);
    int now=1;
    scanf("%d",&m);
    for(int i=1,u;i<=m;i++){
        scanf("%d",&u);
        ans+=lca(now,u);
    }
    printf("%d",ans);
    return 0;
}

以上是9pts的LCA写法，请大家多多指教。