codevs 1036 商务旅行 （LCA）

codevs 1036 商务旅行 （LCA）

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

51 21 53 54 541325

Sample Output

7

思路

所有的道路都是双向的，并且没有环，因此我们可以根据边来建树。

如下图（样例）：

依次经过 ​​1 3​​​ 、 ​​3 2​​​ 、 ​​2 5​​ 这几条路径，从图中我们可以发现，路径的长度刚好等于两端点与其最近公共祖先的深度差之和。

于是：

1->3: dep[1]+dep[3]−2×dep[1]=1+3−2=2

3->2: dep[2]+dep[3]−2×dep[1]=2+3−2=3

2->5: dep[2]+dep[5]−2×dep[1]=2+2−2=2

然后题目便转化为基础的 LCA 问题咯~

AC 代码

#include#include#include#includeusing namespace std;const int maxn=31000;int fa[maxn];int rank[maxn];bool visit[maxn];vector tree[maxn],Qes[maxn];int ancestor[maxn];int ans;int dep[maxn];void init(int n){ memset(rank,0,sizeof(rank)); memset(visit,false,sizeof(visit)); memset(ancestor,0,sizeof(ancestor)); memset(dep,0,sizeof(dep)); ans=0; for(int i=1; i<=n; i++) { fa[i]=i; tree[i].clear(); Qes[i].clear(); }}int find_set(int x) //并查集 查询+路径压缩{ if(x!=fa[x]) fa[x]=find_set(fa[x]); return fa[x];}void union_set(int x,int y) //并查集 合并{ x=find_set(x); y=find_set(y); if(rank[x]>rank[y]) fa[y]=x; else { fa[x]=y; if(rank[x]==rank[y]) rank[y]++; }}void LCA(int u,int pa,int deep){ ancestor[u]=u; dep[u]=deep; int len = tree[u].size(); for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。