juruo在努力学习图论于是看了看这道神题，看着题解思路慢慢磨出了这道神题。

思路好像很清晰可我不会码
觉得dalao代码真是无比清晰了666

总之先去一道差分模板练练手
再来就会轻松很多

大概思路

- 求时间

首先是要求最大值最小，于是就有了二分答案
二分是直接判定该时间是否能完成全部运输
这是主要操作

- 判定操作

首先遍历每条路径长度找出比此时时间要长的路径
记下来进行差分操作（方便判定边的遍历次数）
为啥记这个，是为了判定所有标记边的公共边
然后依题意可以枚举虫洞，来判定此时间是否成立

​

- 基本差分操作 学习资料

直接看代码
有两种差分方式，一种差分点，一种是边；

一种记点的遍历次数，一种是记录遍历边
这里记录边

代码

- 差分

void add(int x,int y,int z)
{
    cnt++;
    edge[cnt].to=y;
    edge[cnt].nt=head[x];
    edge[cnt].w=z;
    head[x]=cnt;

}
void dfs(int x,int fa1,int dd)
{
    deep[x]=dd;fa[x]=fa1;sizee[x]=1;
    for(int i=head[x];i!=-1;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v==fa1)continue;
        d[v]=d[x]+edge[i].w;
        edge_time[v]=edge[i].w;//边转点
        dfs(v,x,dd+1);
        sizee[x]+=sizee[v];
        if(sizee[v]>sizee[son[x]])son[x]=v;//重边
    }
}
void dfs2(int x,int tp)//第二次dfs初始化各结点所在重链的深度最小的结点top（如果不在重链上top就为它自己）
{
    top[x]=tp;
    if(!son[x])return;
    dfs2(son[x],tp);
    for(int i=head[x];i!=-1;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v!=son[x]&&v!=fa[x])
            dfs2(v,v);
    }
}
int lca(int a,int b)
{
    while(top[a]!=top[b])
    {
        if(deep[top[a]]>deep[top[b]])
            a=fa[top[a]];
        else b=fa[top[b]];
    }
    if(deep[a]>deep[b])return b;
    else return a;
}
void dfs3(int x)
{
    for(int i=head[x];i!=-1;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v==fa[x])continue;
        dfs3(v);
        sum[x]+=sum[v];

    }
}

- 处理

void update()
{
    dfs(1,0,1);//第一次dfs初始化出每个结点的深度，父亲及子节点的个数
    dfs2(1,1);
    for(int i=1;i<n;i++)max_dis=max(max_dis,d[i]);//最长路径，用来起始二分
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        s[i]=x;t[i]=y;
        lc[i]=lca(x,y);
        dis[i]=d[x]+d[y]-2*d[lc[i]];//预处理每个路径长度

    }
}
void Add_cf(int x)
{
    sum[s[x]]++;sum[t[x]]++;sum[lc[x]]-=2;
}
int mid;
int check()
{
    memset(sum,0,sizeof(sum));
    int coc=0,max_cha=0;
    for(int i=1;i<=m;i++)
    {
        if(dis[i]>mid)
            Add_cf(i),max_cha=max(max_cha,dis[i]-mid),coc++;
    }
    dfs3(1);//记录每条边被遍历的次数
    for(int i=1;i<=n;i++)//若每条边都经过这边，且这边的对应边时间被减去后能满足mid条件就记下答案
        if(sum[i]>=coc&&max_cha<=edge_time[i])return ans=min(ans,mid);
    return 0;
}
int Two_point()
{
    int l=0,r=max_dis*2;
    while(l<=r)
    {
         mid=(l+r)/2;
         if(check())r=mid-1;
         else l=mid+1;
    }
    return ans;
}

- 总代码

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define N 600005
using namespace std;
int n,m,cnt,fa[N],sizee[N],son[N],deep[N],top[N],sum[N],head[N];
int dis[N],lc[N],max_dis,d[N],ans=(1<<30),edge_time[N],s[N],t[N];
struct node
{
    int nt=-1,to,w;
}edge[N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void add(int x,int y,int z)
{
    cnt++;
    edge[cnt].to=y;
    edge[cnt].nt=head[x];
    edge[cnt].w=z;
    head[x]=cnt;

}
void dfs(int x,int fa1,int dd)
{
    deep[x]=dd;fa[x]=fa1;sizee[x]=1;
    for(int i=head[x];i!=-1;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v==fa1)continue;
        d[v]=d[x]+edge[i].w;
        edge_time[v]=edge[i].w;//边转点
        dfs(v,x,dd+1);
        sizee[x]+=sizee[v];
        if(sizee[v]>sizee[son[x]])son[x]=v;//重边
    }
}
void dfs2(int x,int tp)//第二次dfs初始化各结点所在重链的深度最小的结点top（如果不在重链上top就为它自己）
{
    top[x]=tp;
    if(!son[x])return;
    dfs2(son[x],tp);
    for(int i=head[x];i!=-1;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v!=son[x]&&v!=fa[x])
            dfs2(v,v);
    }
}
int lca(int a,int b)
{
    while(top[a]!=top[b])
    {
        if(deep[top[a]]>deep[top[b]])
            a=fa[top[a]];
        else b=fa[top[b]];
    }
    if(deep[a]>deep[b])return b;
    else return a;
}
void dfs3(int x)
{
    for(int i=head[x];i!=-1;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v==fa[x])continue;
        dfs3(v);
        sum[x]+=sum[v];

    }
}
void update()
{
    dfs(1,0,1);//第一次dfs初始化出每个结点的深度，父亲及子节点的个数
    dfs2(1,1);
    for(int i=1;i<n;i++)max_dis=max(max_dis,d[i]);//最长路径，用来起始二分
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        s[i]=x;t[i]=y;
        lc[i]=lca(x,y);
        dis[i]=d[x]+d[y]-2*d[lc[i]];//预处理每个路径长度

    }
}
void Add_cf(int x)
{
    sum[s[x]]++;sum[t[x]]++;sum[lc[x]]-=2;
}
int mid;
int check()
{
    memset(sum,0,sizeof(sum));
    int coc=0,max_cha=0;
    for(int i=1;i<=m;i++)
    {
        if(dis[i]>mid)
            Add_cf(i),max_cha=max(max_cha,dis[i]-mid),coc++;
    }
    dfs3(1);//记录每条边被遍历的次数
    for(int i=1;i<=n;i++)//若每条边都经过这边，且这边的对应边时间被减去后能满足mid条件就记下答案
        if(sum[i]>=coc&&max_cha<=edge_time[i])return ans=min(ans,mid);
    return 0;
}
int Two_point()
{
    int l=0,r=max_dis*2;
    while(l<=r)
    {
         mid=(l+r)/2;
         if(check())r=mid-1;
         else l=mid+1;
    }
    return ans;
}
int main()
{
    memset(head,-1,sizeof(head));
    n=read();m=read();
    for(int i=1;i<n;i++)
    {
        int x,y,z;
       x=read();y=read();z=read();
        add(x,y,z);
        add(y,x,z);
    }
    update();
   printf("%d",Two_point());

    return 0;
}