LCA（Lowest Common Ancesor)
1.基于二分搜索算法
预处理father[v][k]表示v的2的k次方层祖先，时间复杂度是O（nlogn），每次查询的时间复杂度是O（logn），预处理2k表的技巧在LCA之外也会用到。用链式前向星存图，相对vector邻接表要快。
一次dfs预处理出全部点的父亲结点，然后用2分思想，处理出每个点的2的k次方的父亲结点，对于LCA核心算法，首先把深度较深的移动到与另外一个水平，然后两个结点一起移动，但他们的父亲结点不同时，先上移动，最后返回当前结点的父亲结点。
1.1 Nearest Common Ancestors POJ - 1330
在有根树下，求任意两个结点的LCA，首先找到根节点，以这个结点为起点dfs，预处理出所有结点的父节点。
链式前向星存
#include<iostream>
#include<cstring>
#include<cmath>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N = 1e4 + 5;
int fa[N][15];
int head[N];
int vis[N];
int cur;
int depth[N];
bool Du[N];
int ans[N];
int n;
struct Edge {
int to;
int nex;
}edge[N];
void AddEdge(int u, int v) {
edge[cur].to = v;
edge[cur].nex = head[u];
head[u] = cur++;
}
void init() {
mem(head, -1);
mem(fa, 0);
mem(Du, 0);
mem(depth, 0);
cur = 0;
}
void dfs(int v, int p, int d) {
fa[v][0] = p;
depth[v] = d;
for (int i = head[v]; i != -1; i = edge[i].nex) {
dfs(edge[i].to, v, d + 1);
}
}
int LCA(int s, int t) {
if (depth[s] < depth[t])
swap(s, t);
int temp = depth[s] - depth[t];
for (int i = 0; (1 << i) <= temp; i++)
{
if ((1<<i)&temp)
s = fa[s][i];
}
if (s == t)return s;
for (int i = (int)log2(n*1.0); i >= 0; i--) {
if (fa[s][i] != fa[t][i]) {
s = fa[s][i];
t = fa[t][i];
}
}
return fa[s][0];
}
int main()
{
int T, s, t, root;
cin >> T;
while (T--)
{
init();
cin >> n;
for (int i = 0; i < n - 1; i++) {
cin >> s >> t;
AddEdge(s, t);
Du[t] = 1;
}
for (int i = 1; i <= n; i++){
if (Du[i] == 0){
root = i;
break;
}
}
dfs(root, -1, 0);
for (int j = 0; (1 << (j + 1)) < n; j++) {
for (int i = 1; i <= n; i++) {
if (fa[i][j] < 0)
fa[i][j + 1] = -1;
else fa[i][j + 1] = fa[fa[i][j]][j];
}
}
cin >> s >> t;
cout << LCA(s, t) << endl;
}
}
连接表存
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
const int N = 1e4 + 5;
int father[N][15];
int depth[N];
int Du[N];
int max_log;
struct Node{
vector<int>G;
};
Node tree[N];
void dfs(int v, int p, int d) {
father[v][0] = p;
depth[v] = d;
for (int i = 0; i < tree[v].G.size(); i++) {
if (tree[v].G[i] != p)dfs(tree[v].G[i], v, d + 1);
}
}
void init() {
memset(Du, 0, sizeof(Du));
//for (int i = 0; i < 15; i++)G[i].clear();
memset(tree, 0, sizeof(tree));
memset(depth, 0, sizeof(depth));
memset(father, 0, sizeof(father));
}
int LCA(int u, int v) {
if (depth[u]>depth[v])swap(u, v);
int temp = depth[v] - depth[u];
for (int i = 0; (1 << i) <= temp; i++) {
if ((1 << i)&temp) {//如果temp是1011,1分别左移1,2,3,4位，与temp&，如果当前temp在i为1，说明可以提高i位
v= father[v][i];//depth[v]大，先将v提高与u水平
}
}
if (u == v)return u;
for (int i = max_log; i >= 0; i--) {
if (father[u][i] != father[v][i]) {
u = father[u][i];
v = father[v][i];
}
}
return father[u][0];
}
int main() {
int T, s, t, root;
cin >> T;
while (T--)
{
int n;
cin >> n;
init();
max_log = int(log2(1.0*n));
for (int i = 0; i < n - 1; i++) {
cin >> s >> t;
tree[s].G.push_back(t);
Du[t] = 1;
}
for (int i = 1; i <= n; i++) {
if (Du[i] == 0) {
root = i;
break;
}
}
dfs(root, -1, 0);
for (int j = 0; (1 << (j + 1)) < n; j++) {
for (int i = 1; i <= n; i++) {
if (father[i][j] < 0)
father[i][j + 1] = -1;
else father[i][j + 1] = father[father[i][j]][j];
}
}
cin >> s >> t;
cout << LCA(s, t) << endl;
}
return 0;
}
树上最短距离Factory HDU - 6115
暴力LCA
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define mem(a,x) memset(a,x,sizeof(a))
const int INF = 0x3f3f3f3f;
using namespace std;
const int N = 100010;
int fa[N][25];
int head[N];
int cur;
int depth[N];
int dis[N];//到根节点的距离
vector<int>vec[N];
int n,m;
struct Edge {
int to;
int cost;
int nex;
}edge[2*N];
//edge[i].to表示第i条边的终点,edge[i].nex表示与第i条边同起点的下一条边的存储位置,edge[i].cost为边权值.
//head[i]保存的是以i为起点的所有边中编号最大的那个, 而把这个当作顶点i的第一条起始边的位置
void AddEdge(int u, int v, int w) {
edge[cur].to = v;
edge[cur].cost = w;
edge[cur].nex = head[u];
head[u] = cur++;
}
void init() {
mem(head, -1);
mem(fa, 0);
mem(depth, 0);
mem(dis, 0);
cur = 0;
}
void dfs(int v, int p, int d,int cost) {
fa[v][0] = p;
depth[v] = d;
dis[v] = cost;
for (int i = head[v]; i != -1; i = edge[i].nex) {
if(!depth[edge[i].to])//无向图
dfs(edge[i].to, v, d + 1,dis[v]+edge[i].cost);
}
}
/*
void dfs(int v, int f, int cost)
{
dis[v] = cost;
for (int i = head[v]; i != -1; i = edge[i].nex)
{
int u = edge[i].to;
if (u == f) continue;
if (!depth[u])
depth[u] = depth[v] + 1, fa[u][0] = v, dfs(u, v, dis[v] + edge[i].cost);
}
}
*/
int LCA(int s, int t) {
if (depth[s] < depth[t])
swap(s, t);
int temp = depth[s] - depth[t];
for (int i = 0; (1 << i) <= temp; i++)
{
if ((1 << i)&temp)
s = fa[s][i];
}
if (s == t)return s;
for (int i = (int)log2(n*1.0); i >= 0; i--) {
if (fa[s][i] != fa[t][i]) {
s = fa[s][i];
t = fa[t][i];
}
}
return fa[s][0];
}
int main()
{
int T, s, t,w, root;
scanf("%d", &T);
while (T--)
{
init();
scanf("%d%d", &n, &m);
for (int i = 0; i < n - 1; i++) {
scanf("%d%d%d", &s, &t, &w);
AddEdge(s, t,w);
AddEdge(t, s, w);
//Du[t] = 1;
}
//找到根节点
for (int i = 1; i <= m; i++)
{
int num, v;
scanf("%d", &num);
for (int j = 1; j <= num; j++)
{
scanf("%d", &v);
vec[i].push_back(v);
}
}
//选择1为根
dfs(1, -1,0,0);
for (int j = 0; (1 << (j + 1)) < n; j++) {
for (int i = 1; i <= n; i++) {
if (fa[i][j] < 0)
fa[i][j + 1] = -1;
else fa[i][j + 1] = fa[fa[i][j]][j];
}
}
int q;
scanf("%d",&q);
for (int i = 1; i <= q; i++)
{
int v, u, ans = INF;
scanf("%d%d", &v, &u);
for (int j = 0; j < vec[v].size(); j++)
for (int k = 0; k < vec[u].size(); k++)
ans = min(ans, dis[vec[v][j]] + dis[vec[u][k]] - dis[LCA(vec[v][j], vec[u][k])] * 2);
printf("%d
", ans);
}
for (int i = 1; i <= m; i++) vec[i].clear();
}
return 0;
}