提交记录

Code:

#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = j; i <= k; i++)
using namespace std;
struct edge
{
	int v, w;
};
int head[300001], cn = 0, to[600001];
edge e[600001];
inline void add(int u, int v, int w)
{
	e[++cn] = edge{v, w};
	to[cn] = head[u];
	head[u] = cn;
	return ;
}
inline int read()
{
	char c = getchar();
	int x = 0;
	while (c < '0' || c > '9')
		c = getchar();
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x;
}
int r = 0, n, m, len[300001],u[300001], v[300001], st[300001][20], dep[300001], dis[300001], c[300001], cnt[300001], l[300001];
inline void dfs1(const int &u, const int &fa, const int &w)
{
	dep[u] = dep[fa] + 1, dis[u] = dis[fa] + w;
	st[u][0] = fa;
	rep(i, 1, 19) st[u][i] = st[st[u][i - 1]][i - 1];
	for (int i = head[u]; i; i = to[i])
	{
		if (e[i].v == fa)
			continue;
		dfs1(e[i].v, u, e[i].w);
	}
}
inline int lca(int u, int v)
{
	if (dep[u] < dep[v])
		swap(u, v);
	for (int i = 19; i >= 0; i--)
	{
		if (dep[st[u][i]] < dep[v])
			continue;
		u = st[u][i];
	}
	if (u == v)
		return u;
	for (int i = 19; i >= 0; i--)
	{
		if (st[u][i] == st[v][i])
			continue;
		u = st[u][i], v = st[v][i];
	}
	return st[u][0];
}
inline bool dfs2(const int &u, const int &fa, const int &w, const int &maxn,const int &res)
{
	cnt[u] = c[u];
	bool ans = 0;
	for (int i = head[u]; i; i = to[i])
	{
		if (e[i].v == fa)
			continue;
		ans |= dfs2(e[i].v, u, e[i].w, maxn, res);
		cnt[u] += cnt[e[i].v];
	}
	if (u == 1)
		return ans;
	if (cnt[u] == res && w >= maxn)
		return (ans | 1);
	else
		return ans;
}
inline bool check(const int &k)
{
	memset(c, 0, sizeof c);
	memset(cnt, 0, sizeof cnt);
	int maxn = -1, res = 0;
	rep(i, 1, m)
	{
		if (len[i] <= k)
			continue;
		c[u[i]]++, c[v[i]]++;
		res++;
		c[l[i]] -= 2;
		maxn = max(maxn, len[i] - k);
	}
	bool ans = dfs2(1, 1, 0, maxn, res);
	return ans;
}
signed main()
{
	n = read(), m = read();
	int a, b, t;
	rep(i, 1, n - 1)
	{
		a = read(), b = read();
		t = read();
		add(a, b, t);
		add(b, a, t);
	}
	dfs1(1, 1, 0);
	rep(i, 1, m)
	{
		u[i] = read(), v[i] = read();
		l[i] = lca(u[i], v[i]);
		len[i] = dis[u[i]] + dis[v[i]] - 2 * dis[l[i]];
		r = max(r, len[i]);
	}
	int l = 0;
	r+=1;
	while (l < r)
	{
		int mid = l + r >> 1;
		if (check(mid))
			r = mid;
		else
			l = mid + 1;
	}
	cout << l;
	return 0;
}