定义

在图论和计算机科学中，最近公共祖先是指在一颗树或者一个有向无环图中同时拥有vv和ww作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果vv是ww的后代，那么ww就是vv和ww的最近公共祖先。(来源:维基百科)
如图，是一棵树

每两个点的最近公共祖先一目了然。

用树上倍增求两点的LCA

思想

如图，是一棵树

每两个节点的最近公共祖先一目了然。
假设我们要寻找x,yx,y的最近公共祖先（默认xx的深度比yy的深度大），只需要做到如下步骤：
①利用倍增算法，将xx上升至同yy的相同深度；
②同步上升x,yx,y，直到两节点的父亲节点相同；
③返回此时相同的父亲节点。
father[n][logn]father[n][logn]和每一个节点的深度depth[n]depth[n]可以通过BFS\text{BFS}得到，上升的步骤则利用倍增算法。

用LCA求树上两点的距离

思想

如图，是一棵树

设两点的编号为u,vu,v(默认uu的深度比vv的深度大),两点的位置关系会有如下情况。
定义dis[i]dis[i]为第ii个节点到根节点的距离。
①u,vu,v在一条链上,那么距离为dis[u]−dis[v]dis[u]-dis[v];
②u,vu,v不在一条链上,那么我们必须要先从uu出发,走到u,vu,v的最近公共祖先,再走到vv,此时距离 为dis[u]−dis[lca(u,v)]+dis[v]−dis[lca(u,v)]=dis[u]+dis[v]−2×dis[lca(u,v)]dis[u]-dis[lca(u,v)]+dis[v]-dis[lca(u,v)]=dis[u]+dis[v]-2×dis[lca(u,v)]。
综上所述,u,vu,v的距离始终为dis[u]+dis[v]−2×dis[lca(u,v)]dis[u]+dis[v]-2×dis[lca(u,v)]

模板 HDU 2856 How far away ？

Problem Description

There are nn houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this “How far is it if I want to go from house AA to house BB”? Usually it hard to answer. But luckily in this village the answer is always unique, since the roads are built in the way that there is a unique simple path(“simple” means you can’t visit a place twice) between every two houses. Yout task is to answer all these curious people.

Input

First line is a single integer TT((T<=10T<=10)), indicating the number of test cases.
For each test case,in the first line there are two numbers nn(2≤n≤40000)(2\leq n\leq 40000) and mm (1≤m≤200)(1\leq m\leq 200),the number of houses and the number of queries. The following n−1n-1 lines each consisting three numbers i,j,ki,j,k, separated by a single space, meaning that there is a road connecting house ii and house jj,with length kk(0<k≤40000)(0<k\leq 40000).The houses are labeled from 11 to nn.
Next mm lines each has distinct integers ii and jj, you are supposed to answer the distance between house ii and house jj.

Output

For each test case,output mm lines. Each line represents the answer of the query. Output a bland line after each test case.

Sample Input

2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1

Sample Output

10
25
100
100

Translation

给定一棵 nn 个点的树，mm 次询问，每次询问输出 x,yx,y 两点之间的最短距离。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<algorithm>
#include<cmath>
#include<queue>
#include<iostream>
#define N 40004
using namespace std;
/*-----------------------*/
struct E
{
	int to;
	int w;
	int Next;
}edge[N<<1];
int tot,head[N];
/*-----以上链式前向星-----*/
int n,m;//n个点，m此询问。
int magnitude;//记录数量级
int depth[N];//记录节点深度
int dis[N];//记录节点到根节点的距离
int father[N][20];//记录倍增祖先
/*---------加边-----------*/
void add(int u,int v,int w)
{
	tot++;
	edge[tot].to=v;
	edge[tot].w=w;
	edge[tot].Next=head[u];
	head[u]=tot;
}
/*-------------------------*/
/*----------初始化----------*/
void init()
{
	fill(depth,depth+2+n,0);
	fill(head,head+2+n,-1);
	fill(dis,dis+2+n,0);
	tot=0;
	magnitude=(int)(log(n)/log(2))+1;
}
/*-------------------------*/
/*---------图的遍历---------*/
void bfs()
{
	queue<int>q;
	q.push(1);
	depth[1]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		int i;
		for(i=head[x];i!=-1;i=edge[i].Next)
		{
			int y=edge[i].to;
			if(depth[y]) continue;
			//更新深度和距离
			depth[y]=depth[x]+1;
			dis[y]=dis[x]+edge[i].w;
			int j;
			//初始化
			father[y][0]=x;
			//倍增
			for(j=1;j<=magnitude;j++) 
			{
				father[y][j]=father[father[y][j-1]][j-1];
			}
			q.push(y);
		}
	}
}
/*-----------------------------*/
/*-----------求LCA-------------*/
int lca(int x,int y)
{
	//默认x深度大
	if(depth[x]<depth[y]) swap(x,y);
	int i;
	//x向上倍增  
	for(i=magnitude;i>=0;i--)
	{
		//到达同一深度后退出
		if(depth[father[x][i]]>=depth[y])
		{
			x=father[x][i];
		}
	}
	if(x==y) return x;
	//两者一同向上倍增
	for(i=magnitude;i>=0;i--)
	{
		if(father[x][i]!=father[y][i])
		{
			x=father[x][i];
			y=father[y][i];
		}
	}
	return father[x][0];
}
/*-----------------------------*/
void solve()
{
	cin>>n>>m;
	init();
	int i;
	for(i=1;i<=n-1;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		//建立双向边
		add(u,v,w);
		add(v,u,w);
	}
	bfs();
	//询问
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		cout<<dis[x]+dis[y]-(dis[lca(x,y)]<<1)<<endl; 
	} 
}
int main()
{
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}