题目：https://www.luogu.org/problemnew/show/P2680
因为是最长的时间最短，所以二分！
离线LCA可以知道路径长度。每次只看超过二分值的路径。
原本的想法是遍历一下每条超过二分值的路径，找出“去掉它就能使该路径合法”的那些边，打上标记，最后找到有k个标记的边就能行。
但有点不合适。不需要找出“……”的那些边，而把所有该路径上的边都打上标记，最后找到有k个标记的边的时候判断一下去掉它能不能行。
这样就像均摊了复杂度一样。反正最后都得遍历树，可以那时多做一点、之前少做一点，使时间更好。
注意给边打标记是把它落在它下面的那个点上。而且是LCA的地方-2，和给点打标记不同。
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int N=3e5+5; int n,m,head[N],xnt,cs[N],bh[N],l,r,mx,fa[N],hd[N],xt,dis[N],nw,mid,ans; bool vis[N],flag; struct Ques{ int dis,x,y,lca; }a[N]; struct Edge{ int next,to,w; Edge(int n=0,int t=0,int w=0):next(n),to(t),w(w) {} }edge[N<<1],ed[N<<1]; void add(int x,int y,int z) { edge[++xnt]=Edge(head[x],y,z);head[x]=xnt; edge[++xnt]=Edge(head[y],x,z);head[y]=xnt; } void ad(int x,int y,int z) { ed[++xt]=Edge(hd[x],y,z);hd[x]=xt; ed[++xt]=Edge(hd[y],x,z);hd[y]=xt; } int find(int a){return fa[a]==a?a:fa[a]=find(fa[a]);} bool cmp(Ques a,Ques b){return a.dis>b.dis;} void tarjan(int cr,int f) { vis[cr]=1; for(int i=hd[cr],v;i;i=ed[i].next) if(vis[v=ed[i].to]) { int k=ed[i].w,lc=find(v); a[k].lca=lc;a[k].dis=dis[cr]+dis[v]-2*dis[lc]; mx=max(mx,a[k].dis); } for(int i=head[cr],v;i;i=edge[i].next) if((v=edge[i].to)!=f) { bh[v]=i; dis[v]=dis[cr]+edge[i].w; tarjan(v,cr);fa[v]=cr; } } void solve(int cr) { cs[a[cr].x]++;cs[a[cr].y]++;cs[a[cr].lca]-=2; } int dfs(int cr,int f) { int ret=cs[cr]; for(int i=head[cr],v;i;i=edge[i].next) if((v=edge[i].to)!=f) { ret+=dfs(v,cr);if(flag)return 0; } if(ret==nw&&mx-edge[bh[cr]].w<=mid)flag=1; return ret; } int main() { scanf("%d%d",&n,&m);int x,y,z; for(int i=1;i<n;i++) { scanf("%d%d%d",&x,&y,&z);add(x,y,z); fa[i]=i; } fa[n]=n; for(int i=1;i<=m;i++) { scanf("%d%d",&a[i].x,&a[i].y);ad(a[i].x,a[i].y,i); } tarjan(1,0);sort(a+1,a+m+1,cmp);r=mx; while(l<=r) { mid=((l+r)>>1);memset(cs,0,sizeof cs); for(nw=1;nw<=m&&a[nw].dis>mid;nw++)solve(nw); nw--;flag=0;dfs(1,0); if(flag)ans=mid,r=mid-1; else l=mid+1; } printf("%d",ans); return 0; }