题目大意

给出一个$n$个节点的树，还有$m$条路径，并且保证边权$(t_i)$满足$0\leqslant t_i\leqslant 1000$

要求将任意一条边的边权变为$0$后，询问这$m$条路径上边权总和的最大值最小是多少

数据范围

$n,m\leqslant 300000$

题解

最大值最小问题，理应要二分答案，现在就相当于变成一个判断性问题

是否在将一条边的边权置零之后，每一条路径上边权总和都不超过一个给定的值？

需要预处理出每一条路径上的边权总和$time[i]$，树链剖分或者倍增都可以

假设给定的值为$t$，记录$time[i] > t$的路径，然后在树上求这些路径的交集中边权最大的边

求路径交集可以打个标记，更新节点信息就可以了，具体看代码

接着判断一下，将这条边置零之后是否能够满足条件，最后继续二分答案即可

$P.S.$树链剖分的常数会很大，可能会导致在$UOJ$被卡常

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define maxn 300500
#define lp p<<1
#define rp p<<1|1
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'&&ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,et,cnt;
struct edge{int to,next,c;}e[maxn<<1];
int last[maxn],pos[maxn],v[maxn],t[maxn<<2];
int size[maxn],deep[maxn],f[maxn],top[maxn];
int a[maxn],b[maxn],h[maxn],time[maxn],ord[maxn];
int sum[maxn],mx;

inline void addedge(int u,int v,int c){
    e[++et]=(edge){v,last[u],c};last[u]=et;
    e[++et]=(edge){u,last[v],c};last[v]=et;
}
inline int lca(int u,int v){
    while (1){
        if (top[u]==top[v]) return deep[u]<deep[v]?u:v;
        else if (deep[top[u]]>deep[top[v]]) u=f[top[u]];
        else v=f[top[v]];
    }
}

void dfs(int x){
    size[x]=1;
    goedge(i,x){
        if (e[i].to==f[x]) continue;
        v[e[i].to]=e[i].c;
        deep[e[i].to]=deep[x]+1;
        f[e[i].to]=x;
        dfs(e[i].to);
        size[x]+=size[e[i].to];
    }
}
void gochain(int x,int chain){
    pos[x]=++cnt,top[x]=chain;
    int k=0;
    goedge(i,x)
        if (e[i].to!=f[x]&&size[e[i].to]>size[k]) k=e[i].to;
    if (k) gochain(k,chain);
    goedge(i,x)
        if (e[i].to!=f[x]&&e[i].to!=k) gochain(e[i].to,e[i].to);
}
void build(int p,int wl,int wr){
    if (wl==wr) {t[p]=ord[wl];return;}
    int mid=(wl+wr)>>1;
    build(lp,wl,mid);
    build(rp,mid+1,wr);
    t[p]=t[lp]+t[rp];
}
int query(int p,int wl,int wr,int l,int r){
    if (wl==l&&wr==r) return t[p];
    int mid=(wl+wr)>>1,sum=0;
    if (l<=mid) sum+=query(lp,wl,mid,l,min(mid,r));
    if (r>mid) sum+=query(rp,mid+1,wr,max(l,mid+1),r);
    return sum;
}
inline int query(int low,int high){
    int ans=0;
    while (top[low]!=top[high]){
        ans+=query(1,1,n,pos[top[low]],pos[low]);
        low=f[top[low]];
    }
    ans+=query(1,1,n,pos[high],pos[low]);
    return ans;
}
void dfs2(int x){
    goedge(i,x){
        if (e[i].to==f[x]) continue;
        dfs2(e[i].to);
        sum[x]+=sum[e[i].to];
    }
}
inline int check(int t){
    int tot=0,mx1=0,mx2=0;
    memset(sum,0,sizeof(sum));
    For(i,1,m){
        if (time[i]<=t) continue;
        mx1=max(time[i],mx1);tot++;
        sum[a[i]]+=1,sum[b[i]]+=1;
        sum[h[i]]-=2;
    }
    dfs2(1);
    For(i,1,n) if (sum[i]==tot&&v[i]>mx2) mx2=v[i];
    if (mx1-mx2<=t) return 1;
    else return 0;
}
int main(){
    n=read(),m=read();
    For(i,1,n-1){
        int x=read(),y=read(),z=read();
        addedge(x,y,z);
    }
    dfs(1);gochain(1,1);
    For(i,1,n) ord[pos[i]]=v[i];
    build(1,1,n);
    For(i,1,m){
        a[i]=read(),b[i]=read(),h[i]=lca(a[i],b[i]);
        time[i]=query(a[i],h[i])+query(b[i],h[i])-2*v[h[i]];
        mx=max(mx,time[i]);
    }
    int l=0,r=mx;
    while (l<r){
        int mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}