How far away ？（树上倍增查找最近公共祖先(lca)）

题目链接
前言：在边看题解边wa了近20发后的状态，唉，，，感觉灵魂出窍了
题意：给你一颗由n个点组成的树，再询问m次，每次两个点，问树上两点间的距离。
思路：先将无根树转化为有根树，若两点为a，b，则树上两点的距离就为dist[a]+dist[b]-2*dist[lca(a,b)],其中dist为该节点到根节点的距离。
树上倍增：（明天补）
ac代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define int long long 
struct node {
	int to, w;
};
const int MAXN = 100000 + 5;
vector<node> eg[MAXN];
int dist[MAXN], d[MAXN];
int f[MAXN][30];
int n, m;
void dfs(int a, int fa){
	for (int i = 0; i < eg[a].size(); i++) {
		node g = eg[a][i];
		if (g.to == fa) continue;
		dist[g.to] = dist[a] + g.w;
		d[g.to] = d[a] + 1;
		f[g.to][0] = a;
		dfs(g.to, a);
	}
}
void init() {
	for (int i = 0; i < 20; i++) {
		for (int j = 1; j <= n; j++) {//划重点
			if (f[j][i] < 0) f[j][i + 1] = -1;
			else f[j][i + 1] = f[f[j][i]][i];
		}
	}
}
int lca(int a, int b) {
	if(d[a] > d[b]) swap(a, b);
	for (int i = 0; i < 20; i++) {
		if ((d[b] - d[a]) >> i & 1) {//划重点
			b = f[b][i];
		}
	}
	if (a == b) return a;
	for (int i = 20; i >= 0; i--) {//划重点
		if (f[a][i] != f[b][i]) {
			a = f[a][i], b = f[b][i];
		}
	}
	return f[a][0];
}
signed main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++) eg[i].clear();
		for (int i = 1; i < n; i++) {
			int u, v, w; cin >> u >> v >> w;
			eg[u].push_back(node{ v,w });
			eg[v].push_back(node{ u,w });
		}
		d[1] = 1; f[1][0] = -1;
		dfs(1, -1);
		init();
		for (int i = 0; i < m; i++) {
			int a, b; cin >> a >> b; 
			cout << dist[a] + dist[b] - 2 * dist[lca(a,b)] << endl;;
		}
	}
	return 0;
}

本文地址：https://blog.csdn.net/chineseherofeng/article/details/107216752