codevs 1036 商务旅行
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
某首都城市的商人要经常到各城镇去做生意,他们按自己的路线去做,目的是为了更好的节约时间。
假设有N个城镇,首都编号为1,商人从首都出发,其他各城镇之间都有道路连接,任意两个城镇之间如果有直连道路,在他们之间行驶需要花费单位时间。该国公路网络发达,从首都出发能到达任意一个城镇,并且公路网络不会存在环。
你的任务是帮助该商人计算一下他的最短旅行时间。
输入描述 Input Description
输入文件中的第一行有一个整数N,1<=n<=30 000,为城镇的数目。下面N-1行,每行由两个整数a 和b (1<=a, b<=n; a<>b)组成,表示城镇a和城镇b有公路连接。在第N+1行为一个整数M,下面的M行,每行有该商人需要顺次经过的各城镇编号。
输出描述 Output Description
在输出文件中输出该商人旅行的最短时间。
样例输入 Sample Input
5
1 2
1 5
3 5
4 5
4
1
3
2
5
样例输出 Sample Output
7
#define N 60100
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#define C 20
typedef long long ll;
int ance[N>>][C],dis[N>>],n,a,b,m;
ll sum=;
struct Edge{
int v,last;
}edge[N<<];
int deep[N>>],head[N>>],t=;
void add_edge(int u,int v)
{
++t;
edge[t].v=v;
edge[t].last=head[u];
head[u]=t;
}
void input()
{
scanf("%d",&n);
for(int i=;i<n;++i)
{
scanf("%d%d",&a,&b);
add_edge(a,b);
add_edge(b,a);/*注意树上建边必须是双向的*/
}
}
void dfs(int k)
{
for(int l=head[k];l;l=edge[l].last)
{
if(!deep[edge[l].v])
{
dis[edge[l].v]=dis[k]+;
ance[edge[l].v][]=k;
deep[edge[l].v]=deep[k]+;
dfs(edge[l].v);
}
}
}
void chuli_ance()
{
for(int i=;(<<i)<=n;++i)
for(int j=;j<=n;++j)
ance[j][i]=ance[ance[j][i-]][i-];
}
int lca(int a,int b)
{
int i,j;
if(deep[a]<deep[b]) swap(a,b);
for(i=;(<<i)<=deep[a];++i);
i--;
for(j=i;j>=;--j)
if(deep[a]-(<<j)>=deep[b])
a=ance[a][j];
if(a==b) return a;
for(j=i;j>=;--j)
{
if(ance[a][j]!=-&&ance[a][j]!=ance[b][j])
{
a=ance[a][j];
b=ance[b][j];
}
}
return ance[a][];
}
int main()
{
input();
deep[]=;
dis[]=;
memset(ance,-,sizeof(ance));
dfs();
chuli_ance();
scanf("%d",&m);
scanf("%d",&a);
int sta=a;
for(int i=;i<=m;++i)
{
scanf("%d",&b);
int zuxian=lca(a,b);
sum+=(dis[a]+dis[b]-*dis[zuxian]);
a=b;
}
sum+=dis[sta];
cout<<sum<<endl;
return ;
}