在一棵树上查询任意两个点的最近公共祖先，或求最短距离的离线算法tarjan，基于dfs遍历和并查集，在查询时倍增直到找到最近公共祖先
//裸题：codevs1036 商务旅行 AC代码如下
#include
#include
#include
#include
using namespace std;
int n,m;
int head[30001],next[60001],to[60001],sum;
int deep[30001];
int f[30001][20];//f[i][j]表示第i个点第2^j个祖先；
int S,T;
int ans_lca,ans;
void dfs(int u)//遍历所有节点；
{
for(int i=head[u];i!=0;i=next[i])
{
if(deep[to[i]]==0)
{
deep[to[i]]=deep[u]+1;
f[to[i]][0]=u;
dfs(to[i]);
}
}
}
void init()
{
for(int i=1;(1<
for(int j=1;j<=n;j++)
if(f[j][i-1]) f[j][i]=f[f[j][i-1]][i-1];
}
int lca(int a,int b)
{
int s=a,e=b;
if(deep[s]
int t=0;
while((1<
for(int i=t;i>=0;i--) if(deep[s]-(1<=deep[e]) s=f[s][i];
if(s==e) return s;
for(int i=t;i>=0;i--)
{
if(f[s][i]&&f[s][i]!=f[e][i])
{
s=f[s][i];
e=f[e][i];
}
}
return f[s][0];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {f[i][0]=i;deep[i]=0;}
for(int i=1;i
{
int u,v;
scanf("%d%d",&u,&v);
to[++sum]=v;
next[sum]=head[u];
head[u]=sum;
to[++sum]=u;
next[sum]=head[v];
head[v]=sum;
}
dfs(1);
init();
scanf("%d",&m);
S=1;
for(int i=1;i<=m;i++)
{
if(i>1) S=T;
scanf("%d",&T);
ans_lca=lca(S,T);
ans+=deep[S]+deep[T]-2*deep[ans_lca];
}
printf("%d",ans);
}
