AcWing
3555. 二叉树
最近公共祖先LCA. 首先通过DFS记录树上节点的深度，对于两个待查询的节点，求它们之间的最短距离，就是求它们到最近公共祖先的距离的和。初始化距离res=0，当它们所在深度不同时，对较深的节点单次上跳，res++；此后，让这两个节点同步上跳，直到达到它们的最近公共祖先，对于每次迭代，令res+=2；最后返回res. 树上dfs的时间复杂度为$O(n)$，每次查询的时间复杂度为$O(n)$.
#include <bits/stdc++.h>
using namespace std;
int t, n, m;
const int N = 1010;
int l[N], r[N], fa[N], dist[N];
void dfs(int v, int d){
if(v == -1) return;
dist[v] = d;
dfs(l[v], d + 1);
dfs(r[v], d + 1);
}
int lca(int a, int b){
int res = 0;
if(dist[a] < dist[b]) swap(a, b);
while(dist[a] != dist[b]) a = fa[a], res++;
while(a != b) a = fa[a], b = fa[b], res += 2;
return res;
}
int main(){
cin >> t;
while(t--){
cin >> n >> m;
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= n; i++){
cin >> l[i] >> r[i];
fa[l[i]] = i, fa[r[i]] = i;
}
dfs(1, 0);
for(int i = 1; i <= m; i++){
int a, b;
cin >> a >> b;
int len = lca(a, b);
cout << len << endl;
}
}
return 0;
}