帮同学调没调出来->记录

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
struct edge{int nex,val;};
int n,m,f[25][N],dep[N],d[N],c[N],B[N],E[N],len[N],res;
vector<edge>e[N];
void dfs(int u,int t)
{
    dep[u]=dep[t]+1;
    for(int i=1;(1<<i)<=dep[u];i++)f[i][u]=f[i-1][f[i-1][u]];
    for(auto x:e[u])if(x.nex!=t)f[0][x.nex]=u,d[x.nex]=d[u]+x.val,dfs(x.nex,u);
    return;
}
int lca(int x,int y)
{
    if(dep[x]<dep[y])swap(x,y);
    for(int i=20;i>=0;i--){if(dep[f[i][x]]>=dep[y])x=f[i][x];if(x==y)return x;}
    for(int i=20;i>=0;i--)if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y];
    return f[0][x];
}
int dis(int x,int y)
{
    return d[x]+d[y]-(d[lca(x,y)]<<1);
}
void DFS(int u,int t,int P)
{
    for(auto x:e[u])
    {
        int v=x.nex;
        if(v==t)continue;
        DFS(v,u,P);
        if(c[v]+c[u]==P&&x.val>res)res=x.val;
    }
    for(auto x:e[u])c[u]+=c[x.nex];
    return;
}
bool check(int h)
{
    vector<int>q;
    memset(c,0,sizeof(c));res=-1e9;
    for(int i=1;i<=m;i++)if(len[i]>h)q.push_back(i);
    for(int i:q)c[B[i]]++,c[E[i]]++,c[B[0]=lca(B[i],E[i])]--,c[f[0][B[0]]]--;
    DFS(1,0,q.size());
    for(int i=1;i<=n;i++)if(len[i]-res>h)return 0;
    return 1;
}
void search(int l,int r)
{
    if(l>=r){printf("%d\n",l);return;}
    int mid=l+r>>1;
    if(check(mid))search(l,mid);
    else search(mid+1,r);
    return;
}
signed main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        e[x].push_back({y,z});e[y].push_back({x,z});
    }
    dfs(1,0);
    int Max=-1e9;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&B[i],&E[i]);
        Max=max(Max,len[i]=dis(B[i],E[i]));
    }
    search(0,Max);
    return 0;
}