题目背景
公元 20442044 年,人类进入了宇宙纪元。
题目描述
公元20442044 年，人类进入了宇宙纪元。
L 国有 nn 个星球，还有 n-1n−1 条双向航道，每条航道建立在两个星球之间，这 n-1n−1 条航道连通了 LL 国的所有星球。
小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 u_iui 号星球沿最快的宇航路径飞行到 v_ivi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 jj，任意飞船驶过它所花费的时间为 t_jtj，并且任意两艘飞船之间不会产生任何干扰。
为了鼓励科技创新， LL 国国王同意小 PP 的物流公司参与 LL 国的航道建设，即允许小PP 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 mm 个运输计划。在虫洞建设完成后，这 mm 个运输计划会同时开始，所有飞船一起出发。当这 mm 个运输计划都完成时，小 PP 的物流公司的阶段性工作就完成了。
如果小 PP 可以自由选择将哪一条航道改造成虫洞， 试求出小 PP 的物流公司完成阶段性工作所需要的最短时间是多少？
输入输出格式
输入格式：
第一行包括两个正整数 n, mn,m，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 11 到 nn 编号。
接下来 n-1n−1 行描述航道的建设情况，其中第 ii 行包含三个整数 a_i, b_iai,bi 和 t_iti，表示第 ii 条双向航道修建在 a_iai 与 b_ibi两个星球之间，任意飞船驶过它所花费的时间为 t_iti。数据保证 1 leq a_i,b_i leq n1≤ai,bi≤n 且 0 leq t_i leq 10000≤ti≤1000。
接下来 mm 行描述运输计划的情况，其中第 jj 行包含两个正整数 u_juj 和 v_jvj，表示第 jj 个运输计划是从 u_juj 号星球飞往 v_jvj号星球。数据保证 1 leq u_i,v_i leq n1≤ui,vi≤n
输出格式：
一个整数，表示小 PP 的物流公司完成阶段性工作所需要的最短时间。
输入输出样例
6 3 1 2 3 1 6 4 3 1 7 4 3 6 3 5 5 3 6 2 5 4 5
1#include<bits/stdc++.h>
2#define N 300005
3#define maxd 19
4using namespace std;
5struct Edge{
6 int to,next,val;
7}E[2*N];
8struct node{
9 int l,r,len,lc;
10}pa[2*N];
11inline int get(){
12 char c;
13 while (isspace(c=getchar()));
14 int res=c&15;
15 while (isdigit(c=getchar())) res=(res<<1)+(res<<3)+(c&15);
16 return res;
17}
18bool cmp(node a,node b){
19 return a.len>b.len;
20}
21int Head[2*N],D[2*N],g[N][40],sum_root[2*N],cnt[2*N];
22int x,y,n,m,tot,deld,s,a,b,z,ll,rr,mid,ans,skip,ct,del;
23void addedge(int x,int y,int z){
24 E[++tot]=(Edge){y,Head[x],z};
25 Head[x]=tot;
26}
27void get_deep(int v,int fa,int dep){
28 D[v]=dep;
29 for (int i=Head[v];i;i=E[i].next){
30 if (E[i].to==fa) continue;
31 g[E[i].to][0]=v;
32 get_deep(E[i].to,v,dep+1);
33 }
34}//求出每个点的深度
35void init(){
36 for (int i=1;i<=maxd;i++)
37 for (int j=1;j<=n;j++)
38 g[j][i]=g[g[j][i-1]][i-1];
39}//求出倍增数组
40int LCA(int a,int b){
41 if (D[a]<D[b]) swap(a,b);
42 deld=D[a]-D[b];
43 int i=0;
44 while (deld>0){
45 if (deld&1) a=g[a][i];
46 deld=deld>>1;i++;
47 }
48 if (a==b) return a;
49 for (int i=maxd;~i;i--)
50 if (g[a][i]!=g[b][i]){
51 a=g[a][i];
52 b=g[b][i];
53 }
54 a=g[a][0];b=g[b][0];
55 return a;
56}
57int get_len(int v,int fa,int dis){
58 sum_root[v]=dis;
59 for (int i=Head[v];i;i=E[i].next){
60 if (E[i].to==fa) continue;
61 get_len(E[i].to,v,dis+E[i].val);
62 }
63}//求出每个点到根节点的距离
64int pushdown(int v,int fa){
65 for (int i=Head[v];i;i=E[i].next){
66 if (E[i].to==fa) continue;
67 cnt[v]+=pushdown(E[i].to,v);
68 }
69 return cnt[v];
70}//把差分标记下放（也许应该叫pushup）
71void dfs(int v,int fa){
72 for (int i=Head[v];i;i=E[i].next){
73 if (E[i].to==fa) continue;
74 if (cnt[E[i].to]>=ct&& E[i].val>=del){
75 skip=123; return;
76 }
77 dfs(E[i].to,v);
78 }
79}
80int check(int num){
81 memset(cnt,0,sizeof(cnt));ct=0;skip=0;
82 del=pa[1].len-num;
83 for (int i=1;i<=m;i++){
84 if (pa[i].len<=num) break;
85 cnt[pa[i].l]++;cnt[pa[i].r]++;
86 cnt[pa[i].lc]-=2;
87 ct++;
88 }
89 pushdown(1,0);
90 dfs(1,0);
91 if (skip==123) return 124; else
92 return 123;
93}//对二分的答案进行检查
94void read(){
95 scanf("%d%d",&n,&m);
96 for (int i=1;i<=n-1;i++){
97 x=get();y=get();z=get();
98 addedge(x,y,z);
99 addedge(y,x,z);
100 }
101}
102void solve(){
103 get_deep(1,0,1);
104 init();
105 get_len(1,0,0);
106 for (int i=1;i<=m;i++){
107 x=get();y=get();
108 pa[i].l=x;pa[i].r=y;
109 pa[i].lc=LCA(x,y);
110 pa[i].len=sum_root[x]+sum_root[y]-(sum_root[pa[i].lc]<<1);
111 }
112 sort(pa+1,pa+m+1,cmp);
113 ll=0;ans=rr=pa[1].len+1;
114 while (ll<rr){
115 mid=(ll+rr)>>1;
116 if (check(mid)==123)
117 ll=mid+1; else
118 rr=mid;
119 }
120 cout << ll << endl;
121}
122int main(){
123 read();
124 solve();
125 return 0;
126}