Tarjan ：

只能离线处理，时间复杂度 $O(n+m)$

int get(int x)
{
	if (fa[x] == x) return x;
	return fa[x] = get(fa[x]);
}
void tarjan(int u)
{
	vis[u] = true;
	for (int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to,w=edge[i].w;
		if (vis[v]) continue;
		dis[v] = dis[u] + w;
		tarjan(v);
		fa[v] = u;
	}
	for (int i = head1[u]; i != -1; i = query[i].next)
	{
		int v = query[i].v;
		if (!vis[v]) continue;
		int lca = get(v);//这个即是u和v的LCA
		ans[query[i].id] = dis[v] + dis[u] - 2*dis[lca];//这是两点间的最短距离
	}
}

树上倍增

可以$O(nlog_n)$ 预处理，然后$O(log_n)$ 查询

void bfs()//预处理，也可以dfs
{
	//fat[1][0] = 1;
	queue<int> q;
	q.push(1);
	dep[1] = 1;
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to;
			if (dep[v]) continue;
			dep[v] = dep[u] + 1;
			fat[v][0] = u;
			for (int j = 1; j <= up; j++)
			{
				fat[v][j] = fat[fat[v][j - 1]][j - 1];
			}
			q.push(v);
		}
	}
}
int lca(int u, int v)
{
	if (dep[u] > dep[v]) swap(u, v);
	for (int j = up; j >= 0; j--)
	{
		if (dep[fat[v][j]] >= dep[u]) v = fat[v][j];
	}
	if (u == v) return u;
	for (int j = up; j >= 0; j--)
	{
		if (fat[v][j] !=fat[u][j]){
			v = fat[v][j];
			u = fat[u][j];
		}
	}
	return fat[v][0];
}

LCA转RMQ

首先对树进行深度优先遍历，得到欧拉序以及每个节点首次出现的位置，同时保存深度信息。

• $vs[i]$ : 表示第$i$次访问的节点的编号
• $dep[i]$: 表示第$i$次访问时的深度
• $in[i]$ :节点$i$首次出现在$vs$数组中的位置

询问$u$和$v$的$LCA$,先得到它们俩首次出现的位置区间内$[ in[u],in[v] ]$深度最低的位置下标，记为$pos$，则$vs[pos]$即是他俩的$LCA$。用$ST$表求解即可。

void dfs(int u,int d,int fa)
{
	in[u] = ++top;
	vs[top] = u;
	dep[top] = d;
	for (int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].to, w = edge[i].w;
		if (v==fa) continue;
		dis[v] = dis[u] + w;
		dfs(v, d + 1,u);
		vs[++top] = u;
		dep[top] = d;
	}
}
void RMQ()
{
	for (int i = 0; i <= top; i++)
		dp[i][0] = i;
	for (int j = 1; j <= up; j++)
	{
		for (int i = 1; (i+(1<<j)-1) <= top; i++)
		{
			int p1 = dp[i][j - 1], p2 = dp[i + (1 << (j - 1))][j - 1];
			if (dep[p1] <= dep[p2]){
				dp[i][j] = p1;
			}
			else{
				dp[i][j] = p2;
			}
		}
	}
}
int lca(int l,int r)
{
	if (l > r) swap(l, r);
	int k = log2(r - l + 1);
	int p1 = dp[l][k], p2 = dp[r - (1 << k) + 1][k];
	if (dep[p1] <= dep[p2]) return vs[p1];
	else return vs[p2];
}