# codevs 1036 商务旅行 （LCA）

## Sample Input

5
1 2
1 5
3 5
4 5
4
1
3
2
5


## Sample Output

7


## 思路

1->3: $dep[1]+dep[3]-2×dep[1]=1+3-2=2$

3->2: $dep[2]+dep[3]-2×dep[1]=2+3-2=3$

2->5: $dep[2]+dep[5]-2×dep[1]=2+2-2=2$

## AC 代码

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;

const int maxn=31000;
int fa[maxn];
int rank[maxn];
bool visit[maxn];
vector<int> tree[maxn],Qes[maxn];
int ancestor[maxn];
int ans;
int dep[maxn];

void init(int n)
{
memset(rank,0,sizeof(rank));
memset(visit,false,sizeof(visit));
memset(ancestor,0,sizeof(ancestor));
memset(dep,0,sizeof(dep));
ans=0;
for(int i=1; i<=n; i++)
{
fa[i]=i;
tree[i].clear();
Qes[i].clear();
}
}

int find_set(int x)     //并查集 查询+路径压缩
{
if(x!=fa[x])
fa[x]=find_set(fa[x]);
return fa[x];
}

void union_set(int x,int y)     //并查集 合并
{
x=find_set(x);
y=find_set(y);
if(rank[x]>rank[y])
fa[y]=x;
else
{
fa[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}

void LCA(int u,int pa,int deep)
{
ancestor[u]=u;
dep[u]=deep;
int len = tree[u].size();
for(int i=0; i<len; i++)
{
if(tree[u][i]==pa)continue;
LCA(tree[u][i],u,deep+1);
union_set(u,tree[u][i]);
ancestor[find_set(u)]=u;
}
visit[u]=true;
len = Qes[u].size();
for(int i=0; i<len; i++)
{
if(visit[Qes[u][i]])
ans+=dep[u]+dep[Qes[u][i]]-2*dep[ancestor[find_set(Qes[u][i])]];
}
}

int data[maxn];
int main()
{
int n,m;
while(~scanf("%d",&n))
{
init(n);
for(int i=0; i<n-1; i++)
{
int u,v;
scanf("%d%d",&u,&v);
tree[u].push_back(v);
tree[v].push_back(u);
}
scanf("%d",&m);
for(int i=0; i<m; i++)
{
scanf("%d",data+i);
if(i)
{
Qes[data[i]].push_back(data[i-1]);
Qes[data[i-1]].push_back(data[i]);
}
}
LCA(1,0,1);
printf("%d\n",ans);
}
return 0;
}