很明显，对于树上两点之间的简单路径，他们必然经过 $lca$ 。所以用树上差分维护经过次数即可，最后再暴力模拟修复使用寿命非1的过程，当使用寿命为 $1$ 时，直接将剩余的经过次数加入答案中即可。

时间复杂度：$O(nlogn+klogn)$​

const int maxn = 2e5 + 7, maxm = 21;
int n, k, a[maxn], b[maxn];
struct node
{
	int x, y;
};
vector<node> edge[maxn];
int f[maxn][maxm + 1], d[maxn];

void dfs(int x, int z)
{
	f[x][0] = z;
	for (node y : edge[x])
	{
		if (y.x == z)
			continue;
		a[y.x] = y.y;
		d[y.x] = d[x] + 1;
		dfs(y.x, x);
	}
}

int lca(int x, int y)
{
	if (d[x] < d[y])
		swap(x, y);

	for (int i = maxm; i >= 0; i--)
		if (d[x] - (1 << i) >= d[y])
			x = f[x][i];

	if (x == y)
		return x;

	for (int i = maxm; i >= 0; i--)
		if (f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];

	return f[x][0];
}

void dfs2(int x, int z)
{
	for (node y : edge[x])
	{
		if (y.x == z)
			continue;
		dfs2(y.x, x);
		b[x] += b[y.x];
	}
}

void solve()
{
	cin >> n >> k;
	for (int i = 1; i < n; i++)
	{
		int x, y, z;
		cin >> x >> y >> z;
		edge[x].push_back({y, z});
		edge[y].push_back({x, z});
	}
	dfs(1, 0);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= maxm; j++)
			f[i][j] = f[f[i][j - 1]][j - 1];

	for (int i = 1; i <= k; i++)
	{
		int x, y;
		cin >> x >> y;
		int z = lca(x, y);
		b[x]++, b[y]++, b[z] -= 2;
	}
	dfs2(1, 0);

	int ans = 0;
	for (int i = 2; i <= n; i++)
		while (b[i] >= a[i])
		{
			if (a[i] == 1)
			{
				ans += b[i];
				break;
			}
			b[i] -= a[i];
			a[i] = (a[i] + 1) / 2;
			ans++;
		}
	cout << ans << endl;
}