P8855 [POI2002] 商务旅行

#include <bits/stdc++.h>
using namespace std;
const int N = 50005,L = log2(N);
struct node
{
	int to,nxt;
} e[N];
int n,Q,pre[N],ans = 0,lg2[N],cnt = 0,f[N][L],dep[N];
void add(int x,int y)
{
	e[++cnt].to = y;
	e[cnt].nxt = pre[x];
	pre[x] = cnt;
}
void dfs(int x,int fa)
{
	f[x][0] = fa;
	dep[x] = dep[fa]+1;
	for (int i = pre[x];i;i = e[i].nxt)
	{
		int y = e[i].to;
		if (y != fa) dfs(y,x);
	}
}
int lca(int x,int y)
{
	if (dep[x] < dep[y]) swap(dep[x],dep[y]);
	while (dep[y] < dep[x]) x = f[x][lg2[dep[x]-dep[y]]];
	if (x == y) return x;
	for (int i = L-1;i >= 0;i--)
		if (f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
	return f[x][0];
}
int main()
{
	scanf("%d",&n);
	for (int i = 1;i < n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dep[0] = -1,dfs(1,0);
	lg2[1] = 0;
	for (int i = 2;i <= n;i++) lg2[i] = lg2[i>>1]+1;
	for (int j = 1;j < L;j++)
		for (int i = 1;i <= n;i++) f[i][j] = f[f[i][j-1]][j-1];
	scanf("%d",&Q);
	int now,last = 1;
	while (Q--)
	{
		scanf("%d",&now);
		ans += dep[last] + dep[now] - (dep[lca(last,now)]<<1);
		last = now;
	}
	printf("%d\n",ans);
	return 0;
}