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
题解：
这道题主要是用来巩固lca和倍增算法的，是一道模板题。一个简单的树上倍增，找最近公共祖先。注意局部ans的细节处理，不是对整体相乘，而是对当前步数乘以2。然后借鉴了网上的博客的另一种计算方法：用depth来计算。写第一遍时又把倍增递推写错了。。注意数组开两倍。。
我的方法：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 30005
using namespace std;
int n,m,city[maxn],ans,fist;
int tot,he[maxn],to[maxn*],ne[maxn*];
bool flag[maxn];
int f[][maxn],depth[maxn];
void add(int a,int b)
{
tot++;to[tot]=b;ne[tot]=he[a];he[a]=tot;
}
void build (int x)
{
for (int i=he[x];i;i=ne[i])
if (!flag[to[i]]){
flag[to[i]]=true;
depth[to[i]]=depth[x]+;
f[][to[i]]=x;
build(to[i]);
}
}
void bz()
{
for (int i=;i<=;i++)
for (int j=;j<=n;j++)
f[i][j]=f[i-][f[i-][j]];
}
int lca(int a,int b)
{
int mi=;
if (depth[a]<depth[b]) swap(a,b);
int derta=depth[a]-depth[b];
for (int i=;i<=;i++)
{
if (<<i & derta)
{
mi+=(<<i);
a=f[i][a];
}
}
if (a==b) return mi;
for (int i=;i>=;i--)
{
if (f[i][a]!=f[i][b]) {
a=f[i][a];
b=f[i][b];
int p=(<<i);p*=;//not mi+=(1<<i);mi*=2;
mi+=p;
}
}
a=f[][a];b=f[][b];
mi+=;
return mi;
}
int main()
{
freopen("codevs1036.in","r",stdin);
cin>>n;
for (int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
flag[]=true;
depth[]=;
build();
bz();
cin>>m;cin>>fist;
for (int i=;i<m;i++)
{
int x;scanf("%d",&x);
int y=lca(fist,x);
ans+=y;
fist=x;
}
cout<<ans<<endl;
return ;
}
借鉴方法：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 30005
using namespace std;
int n,m,city[maxn],ans,fist;
int tot,he[maxn],to[maxn*],ne[maxn*];
bool flag[maxn];
int f[][maxn],depth[maxn];
void add(int a,int b)
{
tot++;to[tot]=b;ne[tot]=he[a];he[a]=tot;
}
void build (int x)
{
for (int i=he[x];i;i=ne[i])
if (!flag[to[i]]){
flag[to[i]]=true;
depth[to[i]]=depth[x]+;
f[][to[i]]=x;
build(to[i]);
}
}
void bz()
{
for (int i=;i<=;i++)
for (int j=;j<=n;j++)
f[i][j]=f[i-][f[i-][j]];
}
int lca(int a,int b)
{
//int mi=0;
if (depth[a]<depth[b]) swap(a,b);
int derta=depth[a]-depth[b];
for (int i=;i<=;i++)
{
if (<<i & derta)
{
//mi+=(1<<i);
a=f[i][a];
}
}
if (a==b) return a;
for (int i=;i>=;i--)
{
if (f[i][a]==f[i][b]) continue;
else {
a=f[i][a];
b=f[i][b];
// mi+=(1<<i);mi=(mi<<1);
}
}
// a=f[0][a];b=f[0][b];
//mi+=2;
return f[][a];
}
int main()
{
freopen("codevs1036.in","r",stdin);
cin>>n;
for (int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}
flag[]=true;
depth[]=;
build();
bz();
cin>>m;cin>>fist;
for (int i=;i<m;i++)
{
int x;scanf("%d",&x);
ans+=depth[fist]+depth[x]-*depth[lca(fist,x)];
fist=x;
}
cout<<ans<<endl;
return ;
}