题目大意：
题目分析：
最小化最大值，二分。
二分最短长度mid，将图中链长大于mid的链提取出来，求他们的交路径，选择他们都经过最大的一条边，看是否满足要求。
这是基本思路，下面来想想如何求解：一共尝试了两种办法：
倍增lca / 树链剖分lca + 树上差分： 求lca部分略过（本题用链剖较快），对于一条u->v的路径，在u处+1，v处+1，lca处-2，从下往上求后缀和，即可得到i->fa[i]这条边被经过的次数，假设二分时选出了k条边，那么选择一条经过次数==k的边权最大的边，来判断是否满足。
树链剖分 + 线段树：将u->v上每个节点+1，选出所有的边后，在线段树上将标记下放到底层（节点），如果该节点i（代表i->fa[i]这条边）值为k，更新边权最大值。最后用这个最大值来判断是否满足。
注意:pathModify时，最后一步modify时不能改lca（看代码吧，一言难尽，仔细脑补），因为lca代表的边不是这条路径上的。
大优化： 开一个记忆化数组memory，记录选出最大的k条边时的最大权值和，可以加速很多。
ps: 被uoj的extra test hack掉了。
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO{
inline ll read(){
ll i = 0, f = 1; char ch = getchar();
for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
if(ch == '-') f = -1, ch = getchar();
for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');
return i * f;
}
inline void wr(ll x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}using namespace IO;
typedef long long ll;
const int N = 3e5 + 5, M = 3e5 + 5, OO = 0x3f3f3f3f;
int n, m, ecnt, adj[N], nxt[N << 1], go[N << 1];
int dep[N], sum[N], fa[N], sze[N], idx[N], pos[N], tot, son[N], top[N];
ll ans, len[N << 1], l = OO, r, dis[N], val[N], memory[M];
struct node{
int u, v;
ll tt;
inline bool operator < (const node &b) const{return tt < b.tt;}
}plan[M];
inline void addEdge(int u, int v, ll t){nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v, len[ecnt] = t;}
inline int getLca(int u, int v){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
if(u == v) return u;
return dep[u] < dep[v] ? u : v;
}
inline void dfs1(int u, int f){
dep[u] = dep[f] + 1, fa[u] = f, sze[u] = 1;
for(int e = adj[u], v; e; e = nxt[e]){
if((v = go[e]) == f) continue;
dis[v] = dis[u] + len[e], val[v] = len[e], dfs1(v, u), sze[u] += sze[v];
if(sze[v] > sze[son[u]]) son[u] = v;
}
}
inline void dfs2(int u, int f){
if(son[u]){
idx[pos[son[u]] = ++tot] = son[u];
top[son[u]] = top[u];
dfs2(son[u], u);
}
for(int v, e = adj[u]; e; e = nxt[e]){
if((v = go[e]) == f || v == son[u]) continue;
top[v] = v;
idx[pos[v] = ++tot] = v;
dfs2(v, u);
}
}
inline void getSum(int u, int f){
for(int v, e = adj[u]; e; e = nxt[e]){
if((v = go[e]) == f) continue;
getSum(v, u);
sum[u] += sum[v];
}
}
inline bool check(ll mid){
memset(sum, 0, sizeof sum); int cnt = 0;
for(int i = m; i >= 1; i--){
if(plan[i].tt <= mid) break;
cnt++, sum[plan[i].u]++, sum[plan[i].v]++, sum[getLca(plan[i].u, plan[i].v)] -= 2;
}
if(memory[cnt])
return plan[m].tt - memory[cnt] <= mid;
getSum(1, 0);
ll maxx = 0;
for(int i = 1; i <= n; i++) if(sum[i] == cnt) maxx = max(maxx, val[i]);
memory[cnt] = maxx;
return plan[m].tt - maxx <= mid;
}
inline void solve(){
l = 0, r = plan[m].tt;
while(l <= r){
ll mid = l + r >> 1;
if(check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
}
int main(){
n = read(), m = read();
for(int i = 1; i < n; i++){
int x = read(), y = read(); ll t = 1ll*read();
addEdge(x, y, t), addEdge(y, x, t);
}
pos[1] = top[1] = idx[1] = tot = 1, dfs1(1, 0), dfs2(1, 0);
for(int i = 1; i <= m; i++) plan[i].u = read(), plan[i].v = read(), plan[i].tt = dis[plan[i].u] + dis[plan[i].v] - 2 * dis[getLca(plan[i].u, plan[i].v)];
sort(plan + 1, plan + m + 1);
solve();
wr(ans), putchar('\n');
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace IO{
inline ll read(){
ll i = 0, f = 1; char ch = getchar();
for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
if(ch == '-') f = -1, ch = getchar();
for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');
return i * f;
}
inline void wr(ll x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}using namespace IO;
typedef long long ll;
const int N = 3e5 + 5, M = 3e5 + 5, OO = 0x3f3f3f3f;
int n, m, ecnt, adj[N], nxt[N << 1], go[N << 1];
int dep[N], sum[N], fa[N], sze[N], idx[N], pos[N], tot, son[N], top[N];
ll ans, len[N << 1], l = OO, r, dis[N], val[N], memory[M];
struct node{
int u, v;
ll tt;
inline bool operator < (const node &b) const{return tt < b.tt;}
}plan[M];
namespace SegTree{
int tree[N << 2], tag[N << 2];
inline void upt(int k){tree[k] = tree[k << 1] + tree[k << 1 | 1];}
inline void add(int k, int l, int r, int v){tree[k] += (r - l + 1) * v, tag[k] += v;}
inline void modify(int k, int l, int r, int x, int y){
if(x <= l && r <= y){add(k, l, r, 1);return;}
int mid = l + r >> 1, lc = k << 1, rc = k << 1 | 1;
if(x <= mid) modify(lc, l, mid, x, y);
if(y > mid) modify(rc, mid + 1, r, x, y);
upt(k);
}
inline void pushDown(int k, int l, int r){if(tag[k]) add(k << 1, l, l + r >> 1, tag[k]), add(k << 1 | 1, (l + r >> 1) + 1, r, tag[k]), tag[k] = 0;}
inline void pushToTheEnd(int k, int l, int r, ll v, ll &maxx){
if(l == r){if(tree[k] == v) maxx = max(maxx, val[idx[l]]);return;}
int mid = l + r >> 1, lc = k << 1, rc = k << 1 | 1;
pushDown(k, l, r);
pushToTheEnd(lc, l, mid, v, maxx);
pushToTheEnd(rc, mid + 1, r, v, maxx);
}
}using namespace SegTree;
inline void addEdge(int u, int v, ll t){nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v, len[ecnt] = t;}
inline int getLca(int u, int v){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
if(u == v) return u;
return dep[u] < dep[v] ? u : v;
}
inline void dfs1(int u, int f){
dep[u] = dep[f] + 1, fa[u] = f, sze[u] = 1;
for(int e = adj[u], v; e; e = nxt[e]){
if((v = go[e]) == f) continue;
dis[v] = dis[u] + len[e], val[v] = len[e], dfs1(v, u), sze[u] += sze[v];
if(sze[v] > sze[son[u]]) son[u] = v;
}
}
inline void dfs2(int u, int f){
if(son[u]){
idx[pos[son[u]] = ++tot] = son[u];
top[son[u]] = top[u];
dfs2(son[u], u);
}
for(int v, e = adj[u]; e; e = nxt[e]){
if((v = go[e]) == f || v == son[u]) continue;
top[v] = v;
idx[pos[v] = ++tot] = v;
dfs2(v, u);
}
}
inline void pathModify(int u, int v){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
modify(1, 1, n, pos[top[u]], pos[u]);
u = fa[top[u]];
}
if(dep[u] > dep[v]) swap(u, v);
modify(1, 1, n, pos[son[u]], pos[v]);
}
inline bool check(ll mid){
int cnt = 0;
memset(tree, 0, sizeof tree);
memset(tag, 0, sizeof tag);
for(int i = m; i >= 1; i--){
if(plan[i].tt <= mid) break;
cnt++;
}
if(memory[cnt])
return plan[m].tt - memory[cnt] <= mid;
for(int i = m; i >= m - cnt + 1; i--) pathModify(plan[i].u, plan[i].v);
ll maxx = 0;
pushToTheEnd(1, 1, n, cnt, maxx);
memory[cnt] = maxx;
return plan[m].tt - maxx <= mid;
}
inline void solve(){
l = 0, r = plan[m].tt;
while(l <= r){
ll mid = l + r >> 1;
if(check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
}
int main(){
n = read(), m = read();
for(int i = 1; i < n; i++){
int x = read(), y = read(); ll t = 1ll*read();
addEdge(x, y, t), addEdge(y, x, t);
}
pos[1] = top[1] = idx[1] = tot = 1, dfs1(1, 0), dfs2(1, 0);
for(int i = 1; i <= m; i++) plan[i].u = read(), plan[i].v = read(), plan[i].tt = dis[plan[i].u] + dis[plan[i].v] - 2 * dis[getLca(plan[i].u, plan[i].v)];
sort(plan + 1, plan + m + 1);
solve();
wr(ans), putchar('\n');
return 0;
}