P8855 [POI 2002 R1] 商务旅行

题目描述

某地首都的商人要经常到其他城镇去做生意，他们会按自己的路线去走。

有NNN个城镇，首都编号为111。商人从首都出发，其他各城镇之间都有道路连接。

任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。如果从首都出发，能到达任意一个城镇。

请你求出商人最短的旅行时间。

输入格式

第一行有一个整数NNN，为城镇的数目。

接下来N−1N-1N−1行，每行两个整数aaa和bbb，表示城镇aaa和城镇bbb有公路连接。

接下来一个整数MMM，然后MMM行，每行有该商人需要顺次经过的各城镇编号。

输出格式

一行，输出商人最短的旅行时间。

输入输出样例 #1

输入 #1

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

输出 #1

7

说明/提示

数据范围：1≤N≤300001 \le N \le 300001≤N≤30000。*保证公路网络不会存在环。

C++实现

#include<iostream>#include<vector>usingnamespacestd;vector<int>E[300100];intd[300100],f[300100][30];voiddfs(intu,int_f){d[u]=d[_f]+1;f[u][0]=_f;for(inti=1;i<=20;i++){f[u][i]=f[f[u][i-1]][i-1];}for(intv:E[u]){if(v==_f){continue;}dfs(v,u);}}intLCA(intu,intv){if(d[u]<d[v]){swap(u,v);}for(inti=20;i>=0;i--){if(d[f[u][i]]>=d[v]){u=f[u][i];}}if(u==v){returnu;}for(inti=20;i>=0;i--){if(f[u][i]!=f[v][i]){u=f[u][i];v=f[v][i];}}returnf[u][0];}intmain(){intn,m,u,v,r,s=0;cin>>n;for(inti=1;i<n;i++){cin>>u>>v;E[u].push_back(v);E[v].push_back(u);}dfs(1,0);cin>>m;u=1;while(m--){cin>>v;s+=d[u]+d[v]-2*d[LCA(u,v)];u=v;}cout<<s;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容