题目：https://www.luogu.org/problemnew/show/P2680
久违地1A了好高兴啊！
首先，要最大值最小，很容易想到二分；
判断当前的 mid 是否可行，需要看看有没有去掉一条边使满足的方案；
这就需要树上差分来找出每条边被几个超过 mid 的路线覆盖；
若有一条边正好被所有超过 mid 的路线覆盖，且去掉它之后最大的路线也能满足，就是可行的。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int const maxn=3e5+5; int n,m,head[maxn],ct,cnt,st[maxn],ed[maxn],tag[maxn],lca[maxn],len[maxn]; int h[maxn],ans,mx,f[maxn][20],dep[maxn],l,r,mid; bool flag; struct N{ int to,next,w; N(int t=0,int n=0,int w=0):to(t),next(n),w(w) {} }edge[maxn<<1]; void add(int x,int y,int z){edge[++ct]=N(y,head[x],z); head[x]=ct;} void init(int x,int fa) { f[x][0]=fa; dep[x]=dep[fa]+1; for(int i=1;i<=18;i++)f[x][i]=f[f[x][i-1]][i-1]; for(int i=head[x],u;i;i=edge[i].next) if((u=edge[i].to)!=fa) h[u]=h[x]+edge[i].w, init(u,x); } int LCA(int x,int y) { if(dep[x]<dep[y])swap(x,y); int k=dep[x]-dep[y]; for(int i=0;i<=18;i++) if(k&(1<<i))x=f[x][i]; for(int i=18;i>=0;i--) if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; if(x==y)return x; return f[x][0]; } void dfs(int x) { for(int i=head[x],u;i;i=edge[i].next) { if((u=edge[i].to)==f[x][0])continue; dfs(u); if(flag)return; if(tag[u]==cnt && mx-edge[i].w<=mid)flag=1; tag[x]+=tag[u]; } } bool ck() { cnt=0; flag=0; memset(tag,0,sizeof tag); for(int i=1;i<=m;i++) if(len[i]>mid) { tag[st[i]]++; tag[ed[i]]++; tag[lca[i]]-=2; cnt++; } dfs(1); return flag; } int main() { scanf("%d%d",&n,&m); for(int i=1,x,y,z;i<n;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } init(1,0); for(int i=1;i<=m;i++) { scanf("%d%d",&st[i],&ed[i]); lca[i]=LCA(st[i],ed[i]); len[i]=h[st[i]]+h[ed[i]]-2*h[lca[i]]; mx=max(mx,len[i]); } l=0,r=mx; while(l<=r) { mid=(l+r)>>1; if(ck())ans=mid,r=mid-1; else l=mid+1; } printf("%d",ans); return 0; }