软件工程课

Here.1:
void dfs(int now, int fath) {  //now表示当前节点，fath表示它的父亲节点
	fa[now][0] = fath; depth[now] = depth[fath] + 1;
	for(int i = 1; i <= lg[depth[now]]; ++i)
    	fa[now][i] = fa[fa[now][i-1]][i-1]; 
        //这个转移可以说是算法的核心之一,状态转移
	    //意思是now的2^i祖先等于now的2^(i-1)祖先的2^(i-1)祖先
        //2^i = 2^(i-1) + 2^(i-1)
        
	for(int i = head[now]; i; i = e[i].nex)
    	if(e[i].t != fath) dfs(e[i].t, now);
        //遍历这棵树。
        
}



for(int i = 1; i <= n; ++i) //预先算出log_2(i)+1的值，用的时候直接调用就可以了
	  lg[i] = lg[i-1] + (1 << lg[i-1] == i);  //看不懂的可以手推一下
      
      
      

Here.2:
int LCA(int x, int y) {
	if(depth[x] < depth[y]) //用数学语言来说就是：不妨设x的深度 >= y的深度
		swap(x, y);
	while(depth[x] > depth[y])
		x = fa[x][lg[depth[x]-depth[y]] - 1]; //先跳到同一深度
	if(x == y)  //如果x是y的祖先，那他们的LCA肯定就是x了
		return x;
	for(int k = lg[depth[x]] - 1; k >= 0; --k) //不断向上跳（lg就是之前说的常数优化）
		if(fa[x][k] != fa[y][k])  //因为我们要跳到它们LCA的下面一层，所以它们肯定不相等，如果不相等就跳过去。
	    	x = fa[x][k], y = fa[y][k];
	return fa[x][0];  //返回父节点
}

Here.3:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct zzz {
    int t, nex;
}e[500010 << 1]; int head[500010], tot;

void add(int x, int y) {
	e[++tot].t = y;
	e[tot].nex = head[x];
	head[x] = tot;
}

int depth[500001], fa[500001][22], lg[500001];

void dfs(int now, int fath) {
	fa[now][0] = fath; depth[now] = depth[fath] + 1;
	for(int i = 1; i <= lg[depth[now]]; ++i)
		fa[now][i] = fa[fa[now][i-1]][i-1];
	for(int i = head[now]; i; i = e[i].nex)
		if(e[i].t != fath) dfs(e[i].t, now);
}

int LCA(int x, int y) {
	if(depth[x] < depth[y]) swap(x, y);//找到最深的结点，从最深的结点开始向上跳
	while(depth[x] > depth[y])
		x = fa[x][lg[depth[x]-depth[y]] - 1];//31，32行代码是为了让两个结点跳到同一高度
	if(x == y) return x;
	for(int k = lg[depth[x]] - 1; k >= 0; --k)//两个结点一块倍增往上跳。
		if(fa[x][k] != fa[y][k])
			x = fa[x][k], y = fa[y][k];
	return fa[x][0];
}
int main() {
	int n, m, s; scanf("%d%d%d", &n, &m, &s);
	for(int i = 1; i <= n-1; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		add(x, y); add(y, x);
	}
	for(int i = 1; i <= n; ++i)
		lg[i] = lg[i-1] + (1 << lg[i-1] == i);
	dfs(s, 0);
	for(int i = 1; i <= m; ++i) {
		int x, y; scanf("%d%d",&x, &y);
		printf("%d\n", LCA(x, y));
	}
	return 0;
}