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来计算。写第一遍时又把倍增递推写错了。。注意数组开两倍。。
我的方法：
View Code
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 30005 6 using namespace std; 7 int n,m,city[maxn],ans,fist; 8 int tot,he[maxn],to[maxn*2],ne[maxn*2]; 9 bool flag[maxn]; 10 int f[14][maxn],depth[maxn]; 11 void add(int a,int b) 12 { 13 tot++;to[tot]=b;ne[tot]=he[a];he[a]=tot; 14 } 15 void build (int x) 16 { 17 for (int i=he[x];i;i=ne[i]) 18 if (!flag[to[i]]){ 19 flag[to[i]]=true; 20 depth[to[i]]=depth[x]+1; 21 f[0][to[i]]=x; 22 build(to[i]); 23 } 24 } 25 void bz() 26 { 27 for (int i=1;i<=12;i++) 28 for (int j=1;j<=n;j++) 29 f[i][j]=f[i-1][f[i-1][j]]; 30 } 31 int lca(int a,int b) 32 { 33 int mi=0; 34 if (depth[a]<depth[b]) swap(a,b); 35 int derta=depth[a]-depth[b]; 36 for (int i=0;i<=12;i++) 37 { 38 if (1<<i & derta) 39 { 40 mi+=(1<<i); 41 a=f[i][a]; 42 } 43 } 44 if (a==b) return mi; 45 for (int i=12;i>=0;i--) 46 { 47 if (f[i][a]!=f[i][b]) { 48 a=f[i][a]; 49 b=f[i][b]; 50 int p=(1<<i);p*=2;//not mi+=(1<<i);mi*=2; 51 mi+=p; 52 } 53 } 54 a=f[0][a];b=f[0][b]; 55 mi+=2; 56 return mi; 57 } 58 int main() 59 { 60 freopen("codevs1036.in","r",stdin); 61 cin>>n; 62 for (int i=1;i<n;i++) 63 { 64 int x,y; 65 scanf("%d%d",&x,&y); 66 add(x,y); 67 add(y,x); 68 } 69 flag[1]=true; 70 depth[1]=1; 71 build(1); 72 bz(); 73 cin>>m;cin>>fist; 74 for (int i=1;i<m;i++) 75 { 76 int x;scanf("%d",&x); 77 int y=lca(fist,x); 78 ans+=y; 79 fist=x; 80 } 81 cout<<ans<<endl; 82 return 0; 83 }
借鉴方法：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 30005 6 using namespace std; 7 int n,m,city[maxn],ans,fist; 8 int tot,he[maxn],to[maxn*2],ne[maxn*2]; 9 bool flag[maxn]; 10 int f[14][maxn],depth[maxn]; 11 void add(int a,int b) 12 { 13 tot++;to[tot]=b;ne[tot]=he[a];he[a]=tot; 14 } 15 void build (int x) 16 { 17 for (int i=he[x];i;i=ne[i]) 18 if (!flag[to[i]]){ 19 flag[to[i]]=true; 20 depth[to[i]]=depth[x]+1; 21 f[0][to[i]]=x; 22 build(to[i]); 23 } 24 } 25 void bz() 26 { 27 for (int i=1;i<=12;i++) 28 for (int j=1;j<=n;j++) 29 f[i][j]=f[i-1][f[i-1][j]]; 30 } 31 int lca(int a,int b) 32 { 33 //int mi=0; 34 if (depth[a]<depth[b]) swap(a,b); 35 int derta=depth[a]-depth[b]; 36 for (int i=0;i<=12;i++) 37 { 38 if (1<<i & derta) 39 { 40 //mi+=(1<<i); 41 a=f[i][a]; 42 } 43 } 44 if (a==b) return a; 45 for (int i=12;i>=0;i--) 46 { 47 if (f[i][a]==f[i][b]) continue; 48 else { 49 a=f[i][a]; 50 b=f[i][b]; 51 // mi+=(1<<i);mi=(mi<<1); 52 } 53 } 54 // a=f[0][a];b=f[0][b]; 55 //mi+=2; 56 return f[0][a]; 57 } 58 int main() 59 { 60 freopen("codevs1036.in","r",stdin); 61 cin>>n; 62 for (int i=1;i<n;i++) 63 { 64 int x,y; 65 scanf("%d%d",&x,&y); 66 add(x,y); 67 add(y,x); 68 } 69 flag[1]=true; 70 depth[1]=1; 71 build(1); 72 bz(); 73 cin>>m;cin>>fist; 74 for (int i=1;i<m;i++) 75 { 76 int x;scanf("%d",&x); 77 ans+=depth[fist]+depth[x]-2*depth[lca(fist,x)]; 78 fist=x; 79 } 80 cout<<ans<<endl; 81 return 0; 82 }