新知识：倍增 LCA

刚做一道题：

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

数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开 

最近公共祖先 图论 并查集 线段树 树结构

树链剖分求LCA：

定义：LCA(Lowest Common Ancestor 最近公共祖先)定义如下：在一棵树中两个节点的LCA为这两个节点所有的公共祖先中深度最大的节点。 

代码：
这是一道典型的 LCA，可以使用倍增算法+stl，而stl主要体现在树的存储(std::vector)。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxv=50010,max_log_v=25;
vector<int> G[maxv];// 图的邻接表表示
int parent[maxv][max_log_v],depth[maxv];
// 加边
void add_edge(int from,int to){
	G[from].push_back(to);
	G[to].push_back(from);
} 
void dfs(int root, int v) {// dfs 遍历树并预处理
    depth[v]=depth[root]+1;// 预处理出 parent[0] 和 depth, root 表示根节点的编号
    parent[v][0]=root;
    // 预处理出 parent
    for(int k=1;k<=20;k++)
        parent[v][k]=parent[parent[v][k-1]][k-1];
    for(int k=0;k<G[v].size();k++)
        if(G[v][k]!=root)
        	dfs(v,G[v][k]);
}
int lca(int u,int v) {// 计算u和v的LCA         	
	if(depth[u]>depth[v])swap(u, v);
	for(int k=0;k<=20;k++)
		if((depth[v]-depth[u])>>k&1)
			v=parent[v][k];
        // 利用二分搜索计算 LCA
	if(u==v)return u;
	for(int k=20;k>=0;k--)
		if (parent[u][k]!=parent[v][k]) {
			u=parent[u][k];
			v=parent[v][k];
		}
	return parent[u][0];
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<n;i++) {
		int from,to;
		cin>>from>>to;
		add_edge(from,to);
	}
	dfs(0,1);
	int m;
	cin>>m;
	int st[m+1];
	for(int i=1;i<=m;i++)
		cin>>st[i];
	int ans=0;
	for(int i=2;i<=m;i++)
		ans+=depth[st[i-1]]+depth[st[i]]-2*depth[lca(st[i-1],st[i])];
	cout<<ans<<endl;
	return 0;
}

 倍增 LCA + stl

 和大家分享一下爱这道蛮有趣的题目！