题目大意：给定一棵n个节点的树，输入m组一条链的两个端点；把树上的某个边权改为0，求m条链长度的最大值的最小值；
一.考虑二分：
1.对于需要判断是否为可行方案的 mid，所有链长不大于 mid 的链不会造成影响；
2.故只考虑链长大于 mid 的链是否可以 通过操作使它们的长度不超过mid；
3.对于 2 显然可以得到一个充要条件 —— 存在至少一条边 被所有长度大于 mid 的链覆盖，
在满足上述条件的边中，至少存在一条边，其边权>=最长链的长度-mid
二.问题只剩下如何处理 一.3
边权覆盖次数——树上差分（点权下放：将一条边被覆盖的次数 (即:在差分数组中的权值) 储存在它下方的点
如何记录？—— diff [u] ++ , diff [v]++ , diff [ lca[(u,v)] -=2;
代码如下：（这份代码有很多处理不当的地方，导致常数过大，如：最大链长只需处理一次，差分数组在计算时可记录 dfs 序通过一次循环处理等）
p.s. : 一个奇技淫巧：求 lca 预处理时可能会因为碰到一条链导致爆栈，这时候，不如发挥我们天马行空的想象力,因为大部分人出的链数据都是1->2->3->4……所以把 n/2+1 作为根可以防止栈溢出 (详见luoguP2680)
//Author : 15owzLy1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define lson tl, mid, rt<<1
#define rson mid+1, tr, rt<<1|1
#define pb(__) push_back(__)
#define fr() front()
#define bg() begin()
#define it iterator
#define INF 2100000000
typedef long long ll;
typedef double db;
template<class T>inline void get_max(T &_, T __) { _=_>__?_:__; }
template<class T>inline void get_min(T &_, T __) { _=_<__?_:__; }
template<class T>inline void Swap(T &_, T &__) { T ___=_;_=__;__=___; }
template<class T>inline T abs(T _) { return _>?_:-_; }
template<typename T>inline void read(T &_) {
_=;bool __=;char ___=getchar();
while(___<''||___>''){__|=(___=='-');___=getchar();}
while(___>=''&&___<=''){_=(_<<)+(_<<)+(___^);___=getchar();}
_=__?-_:_;
} const int N = ;
struct node {
int next, to, len;
}edge[N<<];
struct info {
int l, r, lca;
}q[N];
int n, m, head[N], cnt=, fa[N], dis[N], x, y, z, tot, rt;
int dep[N], diff[N], front[N], size[N], hson[N]; inline void add_Edge(int u, int v, int w) {
edge[++cnt].to=v;
edge[cnt].len=w;
edge[cnt].next=head[u];
head[u]=cnt;
} //heavy-light decompostion begin
void get_hson(int u) {
size[u]=;
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].to;
if(fa[u]==v) continue;
dep[v]=dep[u]+, dis[v]=dis[u]+edge[i].len, fa[v]=u;
get_hson(v);
size[u]+=size[v];
if(size[v]>size[hson[u]]) hson[u]=v;
}
} void get_front(int u, int father) {
front[u]=father;
if(hson[u]) get_front(hson[u], father);
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].to;
if(fa[u]==v||hson[u]==v) continue;
get_front(v, v);
}
} inline int lca(int u, int v) {
while(front[u]!=front[v])
if(dep[front[u]]>dep[front[v]]) u=fa[front[u]];
else v=fa[front[v]];
return dep[u]>dep[v]?v:u;
}
//heavy-light decompostion end //work begin
void calc(int u, int &kk, int cnt) {
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].to, w=edge[i].len;
if(v==fa[u]) continue;
calc(v, kk, cnt);
if(diff[v]>=cnt) get_max(kk, w);
diff[u]+=diff[v];
}
} inline int check(int lim) {
int max=, cnt=, max_edge=;
memset(diff, , sizeof(diff));
for(int i=;i<=m;i++)
if(dis[q[i].l]+dis[q[i].r]-*dis[q[i].lca]>lim) {
++cnt;
diff[q[i].l]++, diff[q[i].r]++, diff[q[i].lca]-=;
get_max(max, dis[q[i].l]+dis[q[i].r]-*dis[q[i].lca]);
}
calc(rt, max_edge, cnt);
if(max-max_edge>lim)
return false;
return true;
} inline int Binary_Search(int l, int r) {
int ret=r, mid;
while(l<=r) {
mid=l+r>>;
if(check(mid)) ret=mid, r=mid-;
else l=mid+;
}
return ret;
}
//work end int main() {
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
int max=;
read(n), read(m);
for(int i=;i<n;i++) {
read(x), read(y), read(z);
add_Edge(x, y, z), add_Edge(y, x, z);
}
rt=(n>>)+;
dep[rt]=; get_hson(rt); get_front(rt, rt);
for(int i=;i<=m;i++) {
read(q[i].l), read(q[i].r);
q[i].lca=lca(q[i].l, q[i].r);
get_max(max, dis[q[i].l]+dis[q[i].r]-*dis[q[i].lca]);
}
printf("%d\n", Binary_Search(, max));
fclose(stdin);
fclose(stdout);
return ;
}