This article is made by Jason-Cow.
Welcome to reprint.
But please post the writer's address.
http://www.cnblogs.com/JasonCow/
[NOIP2015]运输计划 Hello!链剖。你好吗？
题意：
给出一棵n个节点的带权树，m对树上点对
现在允许删除一条边，（权值修改为0）
输出: 最小化的点对间最大距离
1.链剖
2.树上差分
3.二分
链剖我就不多说了,就是两dfs
注意：要在dfs1中多维护一个dis[x]，x到root的距离，顺便记录一下w[x]！
void dfs1(int u,int f){
fa[u]=f,dep[u]=dep[f]+,siz[u]=;
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v!=f){
w[v]=E[i].w,dis[v]=dis[u]+E[i].w;
dfs1(v,u);
siz[u]+=siz[v];
if(!son[u]||siz[v]>siz[son[u]])son[u]=v;
}
}
}dfs1
void dfs2(int u,int t){
dfn[u]=++idx,top[u]=t;
if(son[u])dfs2(son[u],t);
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v!=fa[u]&&v!=son[u])dfs2(v,v);
}
}dfs2
树上差分，先差分，后dfs上放（95分的根本原因，不过好写）
细节：add(l,r) <=> cf[l]++ , cf[r+1]--; 再上放
void modify(int u,int f){
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v!=f){
modify(v,u);
cf[u]+=cf[v];
}
}
}modify
二分，很显然好吗。
bool check(int x){
int cnt=,maxcost=;
memset(cf,,sizeof(cf));
for(int i=;i<=m;i++)
if(a[i].dis>x){
cnt++;
maxcost=max(maxcost,a[i].dis-x);
cf[a[i].s]++,cf[a[i].t]++;cf[a[i].lca]-=;
}
if(cnt==)return false;
modify(,);
for(int i=;i<=n;i++)
if(cf[i]==cnt && w[i]>=maxcost)
return false;
return true;
}check
这个还不是正解，因为被卡常了，于是我就卡数据，嘿嘿嘿～～
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std;
const int N=3e5+,M=6e5+;
inline void _(int &ans){
ans=;char x=getchar(),f=;
while(x<''||x>''){if(x=='-')f=;x=getchar();}
while(x>=''&&x<='')ans=ans*+x-'',x=getchar();
if(f)ans=-ans;
} int head[N],tot,n,m;
int dfn[N],top[N],siz[N],son[N],dep[N],fa[N],idx;
int dis[N],w[N],cf[N];
struct node{int v,w,next;}E[M];
struct ask{int lca,dis,s,t;}a[N];
void add(int u,int v,int w){E[++tot]=(node){v,w,head[u]},head[u]=tot;}
void edge(int u,int v,int w){add(u,v,w),add(v,u,w);} void dfs1(int u,int f){
fa[u]=f,dep[u]=dep[f]+,siz[u]=;
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v!=f){
w[v]=E[i].w,dis[v]=dis[u]+E[i].w;
dfs1(v,u);
siz[u]+=siz[v];
if(!son[u]||siz[v]>siz[son[u]])son[u]=v;
}
}
} void dfs2(int u,int t){
dfn[u]=++idx,top[u]=t;
if(son[u])dfs2(son[u],t);
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v!=fa[u]&&v!=son[u])dfs2(v,v);
}
} void lca(int s,int t,int i){
int x=s,y=t;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
a[i].lca=x;
a[i].dis=dis[s]+dis[t]-*dis[x];
} void modify(int u,int f){
for(int i=head[u];i;i=E[i].next){
int v=E[i].v;
if(v!=f){
modify(v,u);
cf[u]+=cf[v];
}
}
} bool check(int x){
int cnt=,maxcost=;
memset(cf,,sizeof(cf));
for(int i=;i<=m;i++)
if(a[i].dis>x){
cnt++;
maxcost=max(maxcost,a[i].dis-x);
cf[a[i].s]++,cf[a[i].t]++;cf[a[i].lca]-=;
}
if(cnt==)return false;
modify(,);
for(int i=;i<=n;i++)
if(cf[i]==cnt && w[i]>=maxcost)
return false;
return true;
} int _u,_v,_w,_s,_t;
int l,r,mid;
int main(){
_(n),_(m);//scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
_(_u),_(_v),_(_w);//scanf("%d%d%d",&_u,&_v,&_w);
edge(_u,_v,_w);
}
dfs1(,);
dfs2(,);
for(int i=;i<=m;i++){
_(_s),_(_t);//scanf("%d%d",&_s,&_t);
a[i].s=_s,a[i].t=_t;
lca(_s,_t,i);
r=max(r,a[i].dis);
}
l=max(,r-);//95分
while(l<=r){
int mid=(l+r)>>;
if(check(mid))l=mid+;
else r=mid-;
}
printf("%d\n",l);
return ;
}