代码思路
主体部分：
初始化，剖分链，求LCA
（也就是dfs1，dfs2，LCA三个函数）
辅助部分：
不需要
简化部分：
暂无
（树链剖分代码其实挺短的，而且足够优美）
（我收回这句话，下面的代码敲了1h）
注意事项：
搜重儿子前要判断u是不是叶子结点
求LCA时比较的是链头深度
原理
对树进行分块（不过是分成链）详
代码注释
以洛谷P3379为例
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5; // 数据范围（节点个数）
int n, m, s, head[N]; // 一些常规的东西
int tot = 0; // 求lca不会用到，但实际常用的dfs序计数器
struct Point{ // 节点信息多的时候会习惯开个结构体来存
int dep, siz, son, top, fath;
// 点的深度 子树大小 重儿子 所在重链的链头 父亲节点
// 没有重儿子则son=0
int id, l, r; // 求lca不会用到，但实际常用的东西
// dfs序 子树dfs编号左右界
void getnum1(Point fa, int f){ // dfs1的初始化
dep = fa.dep+1; siz = 1; fath = f;
// 求深度 初始化字数大小 记录父亲节点
}
void getnum2(int tp){ // dfs2的初始化
id = l = r = ++tot; top = tp;
// 初始化dfs序 记录链头
}
}p[N];
struct Edge{ // 链表存边
int u, v;
}e[N*2]; // 双向边
void dfs1(int u, int fa){ // 第一遍深搜：求节点的各种信息
p[u].getnum1(p[fa], fa); // 初始化
int maxsiz = 0; // 最大的子·子树大小
// ↑用于辅助求重儿子
for(int i = head[u]; i; i = e[i].v){ // 枚举所有边
int v = e[i].u; // 边的端点
if(v == fa) continue; // 辈分不能乱JPG
dfs1(v, u); // 继续往下深搜
p[u].siz += p[v].siz; // 统计子树大小
if(p[v].siz > maxsiz){ // 如果这个儿子更重
maxsiz = p[v].siz; // 更新辅助值
p[u].son = v; // 更新重儿子
}
}
}
void dfs2(int u, int fa, int top){ // 第二遍深搜：统计重链
// top是u所在重链的链头
p[u].getnum2(top); // 初始化
if(p[u].son) dfs2(p[u].son, u, top); // 先搜重儿子以保证dfs序连续
// ↑注意要判断u是不是叶子结点
for(int i = head[u]; i; i = e[i].v){ // 枚举所有边
int v = e[i].u; // 边的端点
if(v == fa || v == p[u].son) continue;
// 不能再搜父亲和重儿子
dfs2(v, u, v); // 轻儿子所在重链的链头是它自己
}
}
int LCA(int u, int v){ // 求u和v的最近公共祖先
while(p[u].top != p[v].top){
// 在同一重链则退出
if(p[p[u].top].dep < p[p[v].top].dep) swap(u, v); // 调整深度
// ↑注意这里比较的是链头的深度
u = p[p[u].top].fath; // 沿着轻边向上跳
}
// 这时候已经在同一个重链上了
// 那么深度小的节点就是LCA
if(p[u].dep < p[v].dep) swap(u, v);
return v; // 返回LCA
}
int main(){ // 喜闻乐见的主函数
// ↓输入
scanf("%d%d%d", &n, &m, &s);
for(int i = 1; i < n; i++){
int u, v; scanf("%d%d", &u, &v);
e[i] = (Edge){v, head[u]}; head[u] = i;
e[i+n] = (Edge){u, head[v]}; head[v] = i+n;
}
// ↑输入
dfs1(s, 0); dfs2(s, 0, s); // 两遍dfs剖出重链
for(int i = 1; i <= m; i++){ // m次询问
int u, v; scanf("%d%d", &u, &v);
printf("%d\n", LCA(u, v)); // 输出答案
}
return 0;
}