1. 题目

传送门=￣ω￣=
题意，给你一棵无根树，再给你一些点对。你现在可以使树上某一条边的长度变为 0，求给出的点对之间的路径中最长的那条路径最短为多长。
数据范围 30W

2. 题解

我太菜了，还要看题解才会

其实主要思路就是：
首先求出所有点对之间的路径长度，设 l[i] 为第 i 个点对之间的路径长度。然后二分答案 ans，找到 l[i] 中所有大于 ans 的，也就是找到对于当前的 ans 不符合要求而必须要使其中某条边变为 0 的路径，然后将这些路径上的所有的边的标记都+1，最后枚举每条边，如果这条边上的标记等于 l[i] 中大于 ans 的 l[i] 的个数，那么说明这条边是所有的不符合要求的路径的公共边，然后就判断能否通过使这条边的长度变为 0 而让所有不符合条件的路径都符合条件（路径长度都小于等于 ans），如果可以的话就说明当前的 ans 是可取的。然而如果所有的公共边都枚举完了而还没出先一条公共边能让所有路径长度都小于等于 ans 的话就说明当前这个 ans 不可取。

具体做法：
对于点对 u,v，求它们之间的路径长度可以先求出它们的 lca，然后设 dis[i] 表示点 i 到根节点的路径长度，那么 u,v 之间的路径长度等于 $dis[u]+dis[v]-2×dis[lca]$
然后我们将 l[i] 求出来，二分答案的上界定为 l[i] 中的最大值，下界定为 0。
二分答案的 check 函数中，我们找出所有长度大于 ans 的路径（设这样的路径条数为 cnt），将这条路径上的所有边的标记都+1，这里可以用数剖，但是慢了，还是用树上差分快一些。然后找出被标记了 cnt 次的边，判断如果把这条边长度变为 0 能否使最长的那条路径的长度小于等于 ans，如果可以则表示这个 ans 符合条件，是个可行的方案。如果所有的被标记了 cnt 次的边中没有一条能变为 0 后使得最长的那条路径长度小于等于 ans 则表明这个 ans 不符合条件，不可行。
最后二分后得到答案。

一些讨论：
1. 为什么只要对当前的 ans 找出长度大于 ans 的路径呢？因为别的路径小于等于 ans，绝对是不会影响到 ans 可不可行的。
2. 为什么标记了 cnt 次的边才看变成 0 能否使 ans 符合条件呢？因为如果一条边没被标记 cnt 次，那么至少存在一条长度大于 ans 的路径不能减少长度从而导致至少有一条路径不符合条件，所以不必讨论标记次数少于 cnt 的边。
3. 为什么只要看最长的路径能否被减少到小于等于 ans 呢？因为我们只会减少公共边，所以所有不符合条件的路径的长度都会减少相同的值，最长的边一定还是最长的边。
4. 怎么标记一条路径？其实只要标记这条路径上的所有的点，然后对于一条边是否标记了 cnt 次，只要看这条边的两个端点是否都被标记了 cnt 次就行了。

代码：

#include <bits/stdc++.h>
#define NS (300005)
#define LGS (20)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct query{int lca,l,u,v;}Q[NS];
struct graph
{
    int head[NS],nxt[NS<<1],to[NS<<1],d[NS<<1],cnt;
    graph(){memset(head,-1,sizeof(head)),cnt=0;}
    void add(int a,int b,int c)
    {
        nxt[cnt]=head[a],to[cnt]=b,d[cnt]=c,head[a]=cnt++;
    }
}G1,G2;
int n,m,fa[NS],pre[NS][LGS+1],dep[NS],dis[NS],val[NS],cal[NS];
bool cmp(query a,query b){return a.l<b.l;}
void init(int a)
{
    pre[a][0]=fa[a],dep[a]=dep[fa[a]]+1;
    for(int i=1;i<=LGS;i++)pre[a][i]=pre[pre[a][i-1]][i-1];
    for(int i=G1.head[a];i!=-1;i=G1.nxt[i])
        if(G1.to[i]!=fa[a])
        {
            dis[G1.to[i]]=dis[a]+G1.d[i],fa[G1.to[i]]=a;
            G2.add(a,G1.to[i],G1.d[i]),init(G1.to[i]);
        }
}
int get_lca(int a,int b)
{
    if(dep[a]>dep[b])swap(a,b);
    for(int i=LGS;i>=0;i--)if(dep[pre[b][i]]>=dep[a])b=pre[b][i];
    if(a==b)return a;
    for(int i=LGS;i>=0;i--)if(pre[a][i]!=pre[b][i])a=pre[a][i],b=pre[b][i];
    return pre[a][0];
}
void calc(int a)
{
    cal[a]=val[a];
    for(int i=G2.head[a];i!=-1;i=G2.nxt[i])calc(G2.to[i]),cal[a]+=cal[G2.to[i]];
}
bool check(int k)
{
    memset(val,0,sizeof(val));
    query p;p.l=k;
    int ub=(int)(upper_bound(Q+1,Q+1+m,p,cmp)-Q);
    if(ub>m)return 1;
    for(int i=ub;i<=m;i++)
    {
        val[Q[i].u]++,val[Q[i].v]++,val[Q[i].lca]--;
        if(fa[Q[i].lca])val[fa[Q[i].lca]]--;
    }
    calc(1);
    for(int i=1;i<=n;i++)if(cal[i]>=m-ub+1)
        for(int j=G2.head[i];j!=-1;j=G2.nxt[j])if(cal[G2.to[j]]>=m-ub+1)
            if(Q[m].l-G2.d[j]<=k)return 1;
    return 0;
}
int main()
{
    IN(n),IN(m);
    for(int i=1,a,b,c;i<n;i++)IN(a),IN(b),IN(c),G1.add(a,b,c),G1.add(b,a,c);
    init(1);
    for(int i=1;i<=m;i++)
    {
        IN(Q[i].u),IN(Q[i].v),Q[i].lca=get_lca(Q[i].u,Q[i].v);
        Q[i].l=dis[Q[i].u]+dis[Q[i].v]-(dis[Q[i].lca]<<1);
    }
    sort(Q+1,Q+1+m,cmp);
    int l=0,r=Q[m].l,mid;
    while(l<r)if(mid=(l+r)>>1,check(mid))r=mid;else l=mid+1;
    printf("%d\n",l);
    return 0;
}