#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5,INF = 1e9;
int n, m;
int fa[N], dep[N], hson[N], sz[N], link[N];
int dfn[N], rnk[N], top[N], dfncnt;
int Left[N], Right[N], section[N], seccnt;

struct edge
{
	int cnt;
	int head[N<<1], nxt[N<<1], to[N<<1], val[N<<1];
	void addE(int x, int y, int z = 0)
	{
		nxt[++cnt] = head[x];
		to[cnt] = y;
		val[cnt] = z;
		head[x] = cnt;
	}
}ed;

struct BinaryIndexedTree
{
	int sum[N];
	int lowbit(int k) { return k & (-k);}
	void update(int x, int k) 
	{ 
		for(int i = x; i <= n; i += lowbit(i)) 
			sum[i] += k;
	}
	int query(int x)
	{ 
		int i = x, res = 0;
		for(int i = x; i >= 1; i -= lowbit(i)) 
			res += sum[i]; 
		return res;
	}
	void build(int x)
	{
		for(int i = 1; i <= n; ++i)
			update(i, link[rnk[i]]);
	}
	int getsum(int l, int r)
	{
		return query(r) - query(l-1);
	}
}BIT;

struct SegmentTree
{
	#define ls (now<<1)
	#define rs (now<<1|1)
	#define mid (s+t>>1)
	int maxx[N<<2], tag[N<<2];
	void up(int now) { maxx[now] = max(maxx[ls], maxx[rs]);}
	void down(int now)
	{
		if(!tag[now]) return;
		tag[ls] = max(tag[ls], tag[now]);
		tag[rs] = max(tag[rs], tag[now]);
		maxx[ls] = max(tag[now], maxx[ls]);
		maxx[rs] = max(tag[now], maxx[rs]);
		tag[now] = 0;
	}
	int getmax(int s, int t, int now, int x)
	{
		if(s == t) return maxx[now];
		down(now);
		return x <= mid ? getmax(s, mid, ls, x) : getmax(mid+1, t, rs, x);
	}
	void update(int s, int t, int l, int r, int now, int val)
	{
		if(l <= s && t <= r)
		{
			maxx[now] = max(maxx[now], val);
			tag[now] = max(tag[now], val);
			return;
		}
		down(now);
		if(l <= mid) update(s, mid, l, r, ls, val);
		if(r > mid) update(mid+1, t, l, r, rs, val);
		up(now);
	}
}ST;

void dfs(int now, int f = 0, int val = 0)
{
	sz[now] = 1;
	fa[now] = f;
	link[now] = val;
	dep[now] = dep[fa[now]] + 1;
	for(int i = ed.head[now]; i; i = ed.nxt[i])
	{
		int v = ed.to[i];
		if(v == f) continue;
		dfs(v, now, ed.val[i]);
		sz[now] += sz[v];
		if(!hson[now] || sz[hson[now]] < sz[v]) hson[now] = v;
	}
}

void deco(int now, int tp)
{
	dfn[now] = ++dfncnt;
	rnk[dfncnt] = now;
	top[now] = tp;
	if(!hson[now]) return;
	deco(hson[now], tp);
	for(int i = ed.head[now]; i; i = ed.nxt[i])
	{
		int v = ed.to[i];
		if(v == fa[now] || hson[now] == v) continue;
		deco(v, v);
	}
}

int path_s, path_t, path_l;
int get_len(int u, int v)
{
	int len = 0;
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		len += BIT.getsum(dfn[top[u]], dfn[u]);
		u = fa[top[u]];
	}
	if(dfn[u] < dfn[v]) swap(u, v);
	if(u != v)len += BIT.getsum(dfn[v]+1, dfn[u]);
	if(len > path_l)
	{
		path_l = len;
		path_s = u;
		path_t = v;
	}
	return len;
}

bool cmp(int a, int b) { return Left[a] < Left[b];}
void update(int u, int v, int len)
{
	seccnt = 0;
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		Left[++seccnt] = dfn[top[u]], Right[seccnt] = dfn[u], section[seccnt] = seccnt;
		u = fa[top[u]];
	}
	if(dfn[u] < dfn[v]) swap(u, v);
	Left[++seccnt] = dfn[v]+1, Right[seccnt] = dfn[u], section[seccnt] = seccnt;
	sort(section+1, section+1+seccnt, cmp);
	if(Left[section[1]] > 1) ST.update(1, n, 1, Left[section[1]]-1, 1, len);
	if(Right[section[seccnt]] < n) ST.update(1, n, Right[section[seccnt]]+1, n, 1, len);
	for(int i = 1; i < seccnt; ++i) ST.update(1, n, Right[section[i]]+1, Left[section[i+1]]-1, 1, len);
}

int ans = INF;
void solve(int u, int v, int len)
{
	if(u == v)
	{
		cout <<"0\n";
		return;
	}
	while(top[u] != top[v])
	{
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		ans = min(ans, max(len-link[u], ST.getmax(1, n, dfn[u], 1)));
		u = fa[u];
	}
	if(dfn[u] < dfn[v]) swap(u, v);
	while(u != v)
	{
		ans = min(ans, max(len-link[u], ST.getmax(1, n, dfn[u], 1)));
		u = fa[u];
	}
	cout << ans;
}

int main()
{
	mt19937 myrand(time(0));
	cin >> n >> m;
	for(int i = 1, x, y, z; i < n; ++i)
	{
		cin >> x >> y >> z;
		ed.addE(x, y, z);
		ed.addE(y, x, z);
	}
	int root = myrand()%n+1;
	dfs(root);
	deco(root, root);
	BIT.build(n);
	for(int i = 1, x, y; i <= m; ++i)
	{
		cin >> x >> y;
		int len = get_len(x, y);
	//	cout << len <<endl;
		update(x, y, len);
	}
	solve(path_s, path_t, path_l);
}

做法和第一篇题解思路基本完全一致，然后rand了个根之后每次输出结果居然都能不一样。。。（样例有时候输出15有时候输出11）