题目大意：
给定一棵有n个节点的有边权树，给定m个运输任务，每个任务从x出发到y，耗时就是树上两点之间的距离。所有运输任务同时开始，总耗时就是最大耗时。
现给一次机会，使某个树边的权值变为0，请选择合适树边，使得处理后，总耗时最小。
输出该最小值。
n<=300000,m<=300000
分析：
暴力60分易得，nmlogn，暴力枚举变权值边即可。
正解：
tarjanLCA + 二分答案 + 树上差分 + 贪心思想
0.离线预处理每个询问两点之间LCA，用tarjan，树剖会卡掉。从而处理出了任意两点之间距离。
1.发现单调性，二分这个最小答案，判断。
2.判断的时候，先找到所有dis值>mid的任务，它们肯定是要通过消掉一条公共边，使得合法的。
3.这个时候用贪心，设len为所有dis中最大值，合法的时候，贪心的要使去掉的公共边是所有公共边中最长的。len-k<=mid才合法。
4.所以要找到k。将所有这次的要处理的tot个任务，放在树上差分。dfs pushup即可。当一个点的权值=tot的时候，它与它父亲之间的边就是一条合法的公共边，所有公共边之间求最大值即可。
一切操作的正确性都易证明。
#include<bits/stdc++.h> #define num ch-'0' using namespace std; const int N=300000+10; const int inf=0x3f3f3f3f; void read(int &x) { x=0;char ch; while(!isdigit(ch=getchar())); for(x=num;isdigit(ch=getchar());x=x*10+num); } int n,m; struct node{ int nxt,to,val; }bian[2*N],edge[2*N]; int hd[N],cnt; int pre[N],cc; bool vis[N]; int dis[N]; int w[N]; struct que{ int x,y; int lca; int dist; }q[N]; int ans; int L,R; int mx,tot; void add1(int x,int y,int z)//树边 { bian[++cnt].nxt=hd[x]; bian[cnt].to=y; bian[cnt].val=z; hd[x]=cnt; } void add2(int x,int y,int z)//询问边 { edge[++cc].nxt=pre[x]; edge[cc].to=y; edge[cc].val=z; pre[x]=cc; } int ff[N]; int fin(int x)//并查集 { if(ff[x]==x) return x; return ff[x]=fin(ff[x]); } void tarjan(int x)//tarjan求 LCA { ff[x]=x; vis[x]=1; for(int i=pre[x];i;i=edge[i].nxt) { int y=edge[i].to; if(vis[y]) { q[edge[i].val].lca=fin(y); } } for(int i=hd[x];i;i=bian[i].nxt) { int y=bian[i].to; if(!vis[y]) { tarjan(y); ff[y]=x; } } } void dfs1(int x,int f,int d,int ds)//处理dis，到根节点距离 { dis[x]=ds; for(int i=hd[x];i;i=bian[i].nxt) { int y=bian[i].to; if(y==f) continue; dfs1(y,x,d+1,ds+bian[i].val); } } void dfs3(int x,int f,int df)//树上差分 { for(int i=hd[x];i;i=bian[i].nxt) { int y=bian[i].to; if(y==f) continue; dfs3(y,x,bian[i].val); w[x]+=w[y]; } if(w[x]==tot){ mx=max(mx,df); } } bool binary(int x)//二分 { memset(w,0,sizeof w); int len=0; tot=0; mx=0; for(int i=1;i<=m;i++) { if(q[i].dist>x) { tot++; w[q[i].x]++,w[q[i].y]++,w[q[i].lca]-=2; len=max(len,q[i].dist); } } dfs3(1,-1,0); if(len-mx<=x) return true; else return false; } int main() { read(n);read(m); int x,y,z; for(int i=1;i<=n-1;i++) { read(x);read(y);read(z); add1(x,y,z); add1(y,x,z); } dfs1(1,-1,1,0); for(int i=1;i<=m;i++) { read(x);read(y); q[i].x=x,q[i].y=y; add2(x,y,i),add2(y,x,i); } tarjan(1); for(int i=1;i<=m;i++) { q[i].dist=dis[q[i].x]+dis[q[i].y]-2*dis[q[i].lca]; R=max(R,q[i].dist); } R+=10; L=0; ans=inf; while(L<=R)//二分答案 { int mid=(L+R)/2; bool fll=binary(mid); if(fll) { ans=min(ans,mid);R=mid-1; } else{ L=mid+1; } } printf("%d",ans); return 0; }