某首都城市的商人要经常到各城镇去做生意，他们按自己的路线去做，目的是为了更好的节约时间。

假设有N个城镇，首都编号为1，商人从首都出发，其他各城镇之间都有道路连接，任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。该国公路网络发达，从首都出发能到达任意一个城镇，并且公路网络不会存在环。

你的任务是帮助该商人计算一下他的最短旅行时间。

输入文件中的第一行有一个整数N，1<=n<=30 000，为城镇的数目。下面N-1行，每行由两个整数a 和b (1<=a, b<=n; a<>b)组成，表示城镇a和城镇b有公路连接。在第N+1行为一个整数M，下面的M行，每行有该商人需要顺次经过的各城镇编号。

在输出文件中输出该商人旅行的最短时间。

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

7

  很裸的最近公共祖先的题目，跑一遍spfa记录首都到各个城市的距离，然后找到两点的最近公共祖先，这样就可以根据距离以及最近公共祖先算出两点的最短路了。

#include<bits/stdc++.h>using namespace std;const int maxn = 30005;int tot = 0,road[maxn],dis[maxn],flag[maxn],vis[maxn],head[maxn],fa[maxn],ancestor[maxn];struct Edge{	int to,next;}edge[maxn<<1];int tt = 0,h[maxn],answer[maxn];struct Query{	int q,next;	int index;}qry[maxn<<1];void init(int N){	for (int i = 0;i <= N;i++)	{		fa[i] = i;ancestor[i] = 0;		vis[i] = false;		head[i] = h[i] = -1;	}}void addedge(int u,int v){	edge[tot] = (Edge){v,head[u]};	head[u] = tot++;}void add_query(int u,int v,int index){	qry[tt] = (Query){v,h[u],index};	h[u] = tt++;	qry[tt] = (Query){u,h[v],index};	h[v] = tt++;}void spfa(){	queue<int>que;	memset(dis,0x3f,sizeof(dis));	memset(flag,false,sizeof(flag));	que.push(1);	dis[1] = 0;	flag[1] = true;	while (!que.empty())	{		int u = que.front();		que.pop();		flag[u] = false;		for (int i = head[u];i != -1;i = edge[i].next)		{			int v = edge[i].to;			if (dis[u] + 1 < dis[v])			{				dis[v] = dis[u] + 1;				if (!flag[v])				{					que.push(v);					flag[v] = true;				}			}		}	}}int find(int x){	int r = x;	while (r != fa[r])	r = fa[r];	int i = x,j;	while (i != r)	{		j = fa[i];		fa[i] = r;		i = j;	}	return r;}void Union(int x,int y){	x = find(x),y = find(y);	if (x == y)	return;	fa[y] = x;}void targin_LCA(int u){	ancestor[u] = u;	vis[u] = true;	for (int i = head[u]; i != -1;i = edge[i].next)	{		int v = edge[i].to;		if (vis[v])	continue;		targin_LCA(v);		Union(u,v);		ancestor[find(u)] = u;	}	for (int i = h[u];i != -1;i = qry[i].next)	{		int v = qry[i].q;		if (vis[v])		{			answer[qry[i].index] = ancestor[find(v)];		}	}	}int main(){	int N,M,u,v,sum = 0;	scanf("%d",&N);	init(N);	for (int i = 1;i < N;i++)	{		scanf("%d%d",&u,&v); 		addedge(u,v);		addedge(v,u);	}	spfa();	scanf("%d",&M);	scanf("%d",&road[0]);	for (int i = 1;i < M;i++)	scanf("%d",&road[i]),add_query(road[i-1],road[i],i);	targin_LCA(1);	for (int i = 1;i < M;i++)	{		sum += dis[road[i]] + dis[road[i-1]] - 2*dis[answer[i]];	}	printf("%d\n",sum);	return 0;}