LOJ2425 NOIP2015 运输计划
题意：给你一颗树，可以将任意一条边的权值变成0，然后求m条路径的长度的最小值
思路：
先二分最后的距离ans，然后我们把路程大于ans的所有路径拿出来
然后把这些路径的交求出来，用树上差分的方法
然后对这个交（用点集转化成边集，就是每个点的上一条边）取一个最大值
然后判断这些边减去这个最大值之后会不会小于等于ans
#include<bits/stdc++.h>
using namespace std;
#define fu(a,b,c) for(int a=b;a<=c;++a)
#define fd(a,b,c) for(int a=b;a>=c;--a)
int read(){
int ans=,w=;char c=getchar();
while(!isdigit(c)&&c!='-')c=getchar();
if(c=='-')w=-,c=getchar();
while(isdigit(c))ans=(ans<<)+(ans<<)+c-'',c=getchar();
return ans*w;
}
const int N=3e5+;
struct Edge{int v,w,next;}E[N<<];
int head[N],tot=;
int n,m,l=,r=;
int cost[N],fro[N],to[N],lca[N];
int dis[N],dep[N],cnt[N],pre[N];
int fa[N][],Log2[N];
void add(int u,int v,int w){E[++tot]=(Edge){v,w,head[u]};head[u]=tot;}
void dfs(int u){
dep[u]=dep[fa[u][]]+;
fu(i,,Log2[dep[u]])fa[u][i]=fa[fa[u][i-]][i-];
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v==fa[u][])continue;
pre[v]=i;
fa[v][]=u;
dis[v]=dis[u]+E[i].w;
dfs(v);
}
}
void redfs(int u){
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v==fa[u][])continue;
redfs(v);
cnt[u]+=cnt[v];
}
}
int LCA(int x,int y){
if(dep[x]<dep[y])swap(x,y);
int t=dep[x]-dep[y];
fu(i,,Log2[t])if(t&(<<i))x=fa[x][i];
if(x==y)return x;
int k=Log2[dep[x]];
while(fa[x][]!=fa[y][]){
if(fa[x][k]!=fa[y][k]){
x=fa[x][k];
y=fa[y][k];
}
k--;
}
return fa[x][];
}
bool check(int vl){
int siz=;
fu(i,,n)cnt[i]=;
fu(i,,m){
if(cost[i]<=vl)continue;
siz++;
cnt[fro[i]]++;
cnt[to[i]]++;
cnt[lca[i]]-=;
}
redfs();
int maxv=;
fu(i,,n){
if(cnt[i]!=siz)continue;
maxv=max(maxv,E[pre[i]].w);
}
fu(i,,m)if(cost[i]-maxv>vl)return ;
return ;
}
int main(){
n=read();m=read();
Log2[]=;fu(i,,n)Log2[i]=Log2[i>>]+;
fu(i,,n-){
int u=read(),v=read(),w=read();
add(u,v,w);
add(v,u,w);
}
dfs();
fu(i,,m){
fro[i]=read(),to[i]=read();
lca[i]=LCA(fro[i],to[i]);
cost[i]=dis[fro[i]]+dis[to[i]]-(dis[lca[i]]<<);
r=max(r,cost[i]);
}
int ans;
while(l<=r){
int mid=(l+r*)/;
if(check(mid))r=mid-,ans=mid;
else l=mid+;
}
printf("%d",ans);
return ;
}