原题链接： https://www.acwing.com/problem/content/523/

抽象出来的题意
给定一个有n个节点，n-1条边的树，给定每条边的权重为t，且给定m个(起点s,终点t)，它们可形成一条路径，现在可以使一条边的权重为0，求出在所有情况下（每条边的权重都可以为0）m个路径的权重和的最大值的最小值。

思路
对于最大值最小，我们可以想到二分，对于这道题，该时间是否可以通过将一条边时间为0使得所有路径任务在该时间内完成可以将区间分为两部分，所以我们可以求能满足该条件的左端点即可。

该怎么判断所有的路径任务在条件下能在mid时间内完成呢？
首先找出所有路径时间(每条路径用树上前缀和+LCA)大于mid的路径，这些路径任务必须要使得路径上的一条边时间为0，因为只能使一条边为0，所以这条边必须为路径的公共边（求公共边用树上差分+LCA），所以使得最大公共边为0最好，我们可以求出要使得每个路径时间小于等于mid要删掉的最小时间数，然后在公共边中看是否有大于等于最小值的即可。

过了19个数据。。。

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef pair<int,int>pii; 
vector<int>e[N];
map<pii,int>mp;
map<pii,int>blca;
int w[N],dist[N];
int dep[N],fa[N][20];

void dfs(int u,int father)
{
    dep[u]=dep[father]+1;
    dist[u]=dist[father]+mp[{u,father}];

    fa[u][0]=father;
    for(int i=1;i<=19;i++)  fa[u][i]=fa[fa[u][i-1]][i-1];

    for(auto t:e[u]){
        if(t==father)   continue;
        dfs(t,u);
    }
}

int lca(int u,int v)
{
    if(dep[u]<dep[v])   swap(u,v);

    for(int i=19;i>=0;i--){
        if(dep[fa[u][i]]>=dep[v])   u=fa[u][i];
    }

    if(u==v)    return v;

    for(int i=19;i>=0;i--){
        if(fa[u][i]!=fa[v][i])  u=fa[u][i],v=fa[v][i];
    }
    return fa[u][0];
}

void dfss(int u,int father)
{
    for(auto t:e[u]){
        if(t==father)   continue;
        dfss(t,u);
        w[u]+=w[t];
    }
}

bool check(int mid)
{
    memset(w,0,sizeof w);

    int cnt=0,mmin=0;
    //遍历所有的任务路径，用lca算出每个路径所用时间从而算出需删掉的最小时间 
    for(auto t:blca)
    {
        int x=t.first.first,y=t.first.second;
        int l=t.second;
        int s=dist[x]+dist[y]-2*dist[l];
        if(s>mid){
            mmin=max(mmin,s-mid);
            w[x]++,w[y]++,w[l]-=2;
            cnt++;
        }
    }
    if(!cnt)    return 1;

    dfss(1,0);

    //注意要遍历所有的边，不能遍历起点和终点blca
    //因为blca存储的是起点和终点对应的lca，不是所有任务路径的边 
    for(auto t:mp)
    {
        int x=t.first.first,y=t.first.second;
        if(dep[x]<dep[y])   swap(x,y);
        if(w[x]==cnt&&mp[t.first]>=mmin)    return 1;
    }
    return 0;
}

int main()
{
    int n,m;cin>>n>>m;
    for(int i=0;i<n-1;i++){
        int a,b,t;scanf("%d%d%d",&a,&b,&t);
        e[a].push_back(b);
        e[b].push_back(a);
        mp[{a,b}]=t;
        mp[{b,a}]=t;
    }

    dfs(1,0);
    for(int i=0;i<m;i++){
        int s,t;scanf("%d%d",&s,&t);
        blca[{t,s}]=blca[{s,t}]=lca(s,t);

    }

    int l=0,r=1e9;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))  r=mid;
        else    l=mid+1;
    }
    cout<<l;
    return 0;
}