Description：

树上 $m$ 条路经，将一条边边权变为 $0$ 使得最长路径最短。

$1\le n,m \le 300000$

Solution：

最长路径最短大概率二分，先二分一个值，然后将比它大的路径用树上差分标记在树上，然后 $dfs$ 一遍统计是否存在一条边被所有边标记，且删掉他能使最长路径满足小于等于 $mid$ ，可以用 $dfs$ 返回值返回子树标记个数，就得到了这条边的标记数。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 300010

struct edge

{

    int to,nxt,v,id;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

struct edge2

{

    int u,v,w,cnt;

}e2[MAXN];

int edgenum2 = 0;

inline void add(int a,int b,int c)

{

    ++edgenum2;e2[edgenum2].u = a;e2[edgenum2].v = b;e2[edgenum2].w = c;

    ++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].id = edgenum2;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    ++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].id = edgenum2;e[edgenum].nxt = lin[b];lin[b] = edgenum;

    return;

}

int top[MAXN],dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN],dis[MAXN];

void dfs1(int k,int depth)

{

    dep[k] = depth;

    siz[k] = 1;

    for(register int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != fa[k])

        {

            dis[e[i].to] = dis[k] + e[i].v;

            fa[e[i].to] = k;

            dfs1(e[i].to,depth + 1);

            siz[k] += siz[e[i].to];

            if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

            {

                son[k] = e[i].to;

            }

        }

    }

    return;

}

void dfs2(int k,int tp)

{

    top[k] = tp;

    if(son[k] == 0)return;

    dfs2(son[k],tp);

    for(register int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != fa[k] && e[i].to != son[k])

        {

            dfs2(e[i].to,e[i].to);

        }

    }

    return;

}

inline int LCA(int a,int b)

{

    while(top[a] != top[b])

    {

        if(dep[top[a]] < dep[top[b]])swap(a,b);

        a = fa[top[a]];

    }

    return (dep[a] < dep[b] ? a : b);

}

int u[MAXN],v[MAXN],maxd = -1;

inline int d(int a,int b){return dis[a] + dis[b] - 2 * dis[LCA(a,b)];}

int basket_add[MAXN],basket_dec[MAXN];

inline void mark(int a,int b)

{

    ++basket_add[a];

    ++basket_add[b];

    ++basket_dec[LCA(a,b)];

    ++basket_dec[LCA(a,b)];

    return;

}

int dfs(int k)

{

    register int cur = 0;

    for(register int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(e[i].to != fa[k])

        {

            e2[e[i].id].cnt = dfs(e[i].to);

            cur += e2[e[i].id].cnt;

        }

    }

    cur += basket_add[k];

    cur -= basket_dec[k];

    return cur;

}

inline bool check(int k)

{

    memset(basket_add,0,sizeof(basket_add));

    memset(basket_dec,0,sizeof(basket_dec));

    register int tot = 0;

    for(register int i = 1;i <= m;++i)

    {

        if(d(u[i],v[i]) > k)

        {

            mark(u[i],v[i]);

            ++tot;

        }

    }

    dfs(1);

    for(register int i = 1;i < n;++i)

    {

        if(e2[i].cnt == tot && e2[i].w >= maxd - k)

        {

            return true;

        }

    }

    return false;

}

inline int read()

{

    register int res = 0;

    register char c = getchar();

    while(!isdigit(c))c = getchar();

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res;

}

int main()

{

    scanf("%d%d",&n,&m);

    int a,b,c;

    for(int i = 1;i < n;++i)

    {

        a = read();b = read();c = read();

        add(a,b,c);

    }

    dfs1(1,1);

    dfs2(1,1);

    for(int i = 1;i <= m;++i)

    {

        u[i] = read();v[i] = read();

        maxd = max(maxd,d(u[i],v[i]));

    }

    int l = 0,r = n * 1000,mid;

    while(l < r)

    {

        mid = ((l + r) >> 1);

        if(check(mid))r = mid;

        else l = mid + 1;

    }

    printf("%d\n",l);

    return 0;

}