题目链接： https://acm.uestc.edu.cn/problem/tun-tu-liang/description

题目大意：给你一棵树，让你求两个点之间的边的最小值

分析：

这道题一眼看过去，最近公共祖先（LCA）

既然是LCA，那么就可以使用倍增法来做

代码大概就是先dfs建边，然后倍增

处理询问时，先让两个点上升到同一高度，然后若父亲还不同则倍增

这道题还有一种做法是树链剖分，但是代码会相对长很多

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
const int INF = 1000000001;
struct edge
{
	int to, cost;
};
vector<edge> G[MAXN];
int father[MAXN][20];
int minnum[MAXN][20];
int depth[MAXN];
void dfs(int v,int _father,int _cost,int dp)
{
	father[v][0] = _father; minnum[v][0] = _cost; depth[v] = dp;
	int len = G[v].size();
	for (int i = 0; i < len; i++)
	{
		if (G[v][i].to != _father)
		{
			dfs(G[v][i].to,v, G[v][i].cost,dp+1);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	int n, q,a,b,c,nowmin;
	edge linshibian;
	cin >> n >> q;
	for (int i = 1; i < n; i++)
	{
		cin >> a >> b >> c;
		linshibian.to = b;
		linshibian.cost = c;
		G[a].push_back(linshibian);
		linshibian.to = a;
		G[b].push_back(linshibian);
	}
	dfs(n/2,-1,INF,1);
	for (int k = 1; k < 20; ++k)
	{
		for (int i = 1; i <= n; i++)
		{
			father[i][k] = father[father[i][k - 1]][k - 1];
			minnum[i][k] = min(minnum[i][k-1], minnum[father[i][k - 1]][k-1]);
		}
	}
	for (int i = 0; i < q; i++)
	{
		cin >> a >> b;
		nowmin = INF;
		if (a == b)nowmin = 0;
		if (depth[a] > depth[b])swap(a, b);
		for (int k = 19; depth[b] > depth[a]; --k)
		{
			if ((depth[b] - depth[a]) >> k & 1)
			{
				nowmin = min(nowmin, minnum[b][k]);
				b = father[b][k];
			}
		}
		if (a != b)
		{
			for (int k = 19; k >= 0; --k)
			{
				if (father[a][k] != father[b][k])
				{
					nowmin = min(nowmin, min(minnum[a][k], minnum[b][k]));
					a = father[a][k];
					b = father[b][k];
				}
			}
			nowmin = min(nowmin, min(minnum[a][0], minnum[b][0]));
		}
		cout << nowmin << endl;
	}
	return 0;
}