LCA(Lowest Common Ancestor 最近公共祖先)定义如下：在一棵树中两个节点的LCA为这两个节点所有的公共祖先中深度最大的节点。
比如这棵树
结点5和6的LCA是2,12和7的LCA是1,8和14的LCA是4。
这里讲一下用树链剖分来求LCA。
先想一下，若要求结点13和4的LCA，那很显然是4，因为他们在一条重链上。所谓的重链，就是取每个结点u的所有子节点中，子树最大的子结点v，然后将边(u,v)作为重边，其余边作为轻边，重边构成的链就是重链。子树最大就是指该点所得孩子结点最多（这里要包括他自己）。
我们先找出所有的重链。
可见这棵树有7条重链（包括一条链只有一个结点的）。每一条重链的顶点就是该链上深度最小的结点。
而树链剖分的目标就是将要求的两个点转换到一条重链上，这样LCA就是该条重链上深度较小的结点了。
具体实现步骤拿第一幅图中的结点12和14举例。首先要比较的是12和14所在链的顶点的深度，可见12所在链的顶点更深，此时将12跳到它的顶点12的父亲结点6。然后再比较6所在链的顶点和14所在链的顶点，循环下去直到两个点到同一个链上，最后比较，收尾。
这就是树链剖分的基本思想了，那我就开始写了。
首先跑两遍dfs，第一遍是建树和建链，第二遍是记录每一个结点的顶点（这样就知道该点所在链的顶点的深度了）。然后就是用上述思想求LCA。
我们以洛谷的板子为例，传送门：https://www.luogu.org/problemnew/show/P3379
上代码（懒得用邻接表存图了，上vector）
其中vis数组是为了解决无向图存两次边的问题。
1 #include<cstdio>
2 #include<iostream>
3 #include<cmath>
4 #include<algorithm>
5 #include<cstring>
6 #include<vector>
7 using namespace std;
8 const int maxn = 5e5 + 5;
9 vector<int>v[maxn];
10 /*第一遍dfs主要来维护以下这些数组，size[now]指结点now的子树大小，dep[now]指结点now的深度，
11 Maxson[now]指now所在链上结点now的下一个结点（用来建链） */
12 int vis[maxn], size[maxn], dep[maxn], fa[maxn], Maxson[maxn];
13 void dfs1(int now)
14 {
15 vis[now] = 1; size[now]= 1;
16 for(int i = 0; i < v[now].size(); ++i)
17 if(!vis[v[now][i]])
18 {
19 dep[v[now][i]] = dep[now] + 1;
20 fa[v[now][i]] = now;
21 dfs1(v[now][i]);
22 size[now] += size[v[now][i]]; //结点now的子树大小就是他所有孩子结点的大小之和加1（包括自己）
23 if(size[v[now][i]] > size[Maxson[now]]) Maxson[now] = v[now][i]; //选重边
24 }
25 }
26 int path[maxn];
27 void dfs2(int now)
28 {
29 vis[now] = 1;
30 for(int i = 0; i < v[now].size(); ++i)
31 if(!vis[v[now][i]])
32 {
33 if(Maxson[now] == v[now][i]) path[v[now][i]] = path[now];
34 else path[v[now][i]] = v[now][i]; //新开辟一条链
35 dfs2(v[now][i]);
36 }
37 }
38 int lca(int x, int y)
39 {
40 while(path[x] != path[y]) //若不在一条链上
41 {
42 if(dep[path[x]] > dep[path[y]]) x = fa[path[x]];
43 else y = fa[path[y]];
44 }
45 return dep[x] < dep[y] ? x : y;
46 }
47 int main()
48 {
49 int n, m, s; scanf("%d%d%d", &n, &m, &s);
50 for(int i = 1; i < n; ++i)
51 {
52 int a, b; scanf("%d%d", &a, &b);
53 v[a].push_back(b); v[b].push_back(a);
54 }
55 dep[s] = 0; memset(vis, 0, sizeof(vis));
56 dfs1(s);
57 path[s] = s; memset(vis, 0, sizeof(vis));
58 dfs2(s);
59 for(int i = 1; i <= m; ++i)
60 {
61 int a, b; scanf("%d%d", &a, &b);
62 printf("%d\n", lca(a, b));
63 }
64 return 0;
65 }