https://www.luogu.org/problem/show?pid=2680
题解：：二分最大值，判断出所有大于最大值的路径的交，再判断能否达到最大值以下。求路径的交用树上前缀和，每次判断是O（n）的，总复杂度为O（nlogn）；
#include<cstdio> #include<cstring> #include<algorithm> #define maxn 300010 #define re register using namespace std; template<class T>inline void read(T &x) { x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=f?-x:x; return; } struct Node { int u,v,sum,l; inline bool operator<(const Node&A)const{ return A.sum<sum; } }q[maxn]; int n,m,size[maxn],d[maxn],dis[maxn],cnt,pos[maxn],id,head[maxn],top[maxn],fa[maxn],dep[maxn],son[maxn]; struct node{int v,w,next;}e[600010]; inline void ins(int u,int v,int w){e[++cnt].v=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;} void dfs1(int x) { size[x]=1; for(re int p=head[x];p;p=e[p].next) { int v=e[p].v; if(fa[x]==v)continue; fa[v]=x;dep[v]=dep[x]+1;dis[v]=dis[x]+e[p].w; dfs1(v); size[x]+=size[v]; if(size[v]>size[son[x]])son[x]=v; } } void dfs2(int x,int chain) { top[x]=chain;pos[++id]=x; if(!son[x])return; dfs2(son[x],chain); for(re int p=head[x];p;p=e[p].next) if(e[p].v!=fa[x]&&e[p].v!=son[x])dfs2(e[p].v,e[p].v); } int lca(int x,int y) { while(top[x]!=top[y]) if(dep[top[x]]>dep[top[y]])x=fa[top[x]]; else y=fa[top[y]]; return dep[x]<dep[y]?x:y; } bool check(int x) { int t=0,Max=0; if(x>=q[1].sum)return true; memset(d,0,sizeof(d)); for(re int i=1;i<=m;i++) { if(q[i].sum>x) { t++; d[q[i].u]++;d[q[i].v]++;d[q[i].l]-=2; } else break; } for(re int i=n;i>=1;i--) d[fa[pos[i]]]+=d[pos[i]]; for(re int i=2;i<=n;i++) if(d[i]==t)Max=max(Max,dis[i]-dis[fa[i]]); if(q[1].sum-Max>x)return false; return true; } int main() { int u,v,w; read(n);read(m); for(re int i=1;i<n;i++) { read(u);read(v);read(w); ins(u,v,w);ins(v,u,w); } dfs1(1); dfs2(1,1); for(re int i=1;i<=m;i++) { read(u);read(v); q[i].u=u;q[i].v=v; q[i].l=lca(u,v); q[i].sum=dis[u]+dis[v]-2*dis[q[i].l]; } sort(q+1,q+1+m); int l=0,r=q[1].sum,mid; while(l<r) { mid=l+r>>1; if(check(mid))r=mid; else l=mid+1; } printf("%d ",r); return 0; }