http://172.20.6.3/Problem_Show.asp?id=1454
从这道题我充分认识到我的脑子里好多水orz。
如果知道了这个要用二分和差分写，就没什么思考上的难点了（屁咧你写了一个下午）。
下面讲述一下我写这道题的辛酸历程：
我最开始写了个树链剖分+线段树+二分+差分数组，tle了一个点，这完全搞不懂啊，什么鬼啊，为什么啊，不然你告诉我怎么写啊。
然后我去找了a了此题的Lcentury大神，然后他告诉我：“这个题要用tarjan求lca啊，都什么年代了还用树链剖分，tanjan快啊，你这肯定要超时的。”然后我就信了Lcentury大神的邪学了一波tanjan。
我还很奇怪，tanjan怎么求两点之间距离啊？？？等到我辛辛苦苦读了一遍tanjan求两点距离的写法之后，狂喷凌霄血，原来只要找到lca一减就出来了，所以说树链剖分找lca是不会tle的，tle是因为我多加了一个sb线段树。
所以我两种都写了一遍[二哈]，事实证明两种方案速度的确没有差很多。。。大数据一个是2609ms一个是2640ms。
下面展示我的两个代码（mdzz），就当mark模板了。
tanjan
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
#define lc x*2
#define rc x*2+1
const int maxn=;
int n,m;
struct nod{
int next,y,v;
}e[maxn*];
int head[maxn]={},tot=;
struct wtf{
int x,y,fa,v;
}a[maxn];
struct node{
int y,id,next;
}d[maxn*];
int lin[maxn]={};
int fa[maxn]={};
int f[maxn]={};
int cnt,ned;
int vis[maxn]={};
int dis[maxn]={};
inline void init(int x,int y,int v){
e[++tot].y=y;
e[tot].v=v;
e[tot].next=head[x];
head[x]=tot;
} inline void insert(int x,int y,int id){
d[++tot].y=y;
d[tot].id=id;
d[tot].next=lin[x];
lin[x]=tot;
}
int read(){
char ch=getchar();int x=,f=;
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch<=''&&ch>=''){x*=;x+=ch-'';ch=getchar();}
return x*f;
}
int find(int x){
if(f[x]==-)
return x;
return f[x]=find(f[x]);
}
void merge(int u,int v){
int x=find(u);
int y=find(v);
if(x!=y) f[x]=y;
}
void tarj(int x){
int y,v;
fa[x]=x;
vis[x]=;
for(int i=head[x];i;i=e[i].next){
y=e[i].y;v=e[i].v;
if(vis[y])continue;
dis[y]=dis[x]+v;
tarj(y);
merge(x,y);
fa[find(x)]=x;
}
for(int i=lin[x];i;i=d[i].next){
y=d[i].y;
if(vis[y])
a[d[i].id].fa=fa[find(y)];
}
}
bool mmp(wtf aa,wtf bb){
return aa.v>bb.v;
}
void dfs3(int x,int pa,int val){
int y,v;
for(int i=head[x];i;i=e[i].next){
y=e[i].y;v=e[i].v;
if(y==pa)continue;
dfs3(y,x,v);
vis[x]+=vis[y];
}
// cout<<ned<<vis[x]<<val<<x<<endl;
if(vis[x]==ned)cnt=max(cnt,val);
}
inline bool check(int x){
cnt=;
memset(vis,,sizeof(vis));
for(int i=;i<=m;i++){
if(a[i].v>x){
vis[a[i].x]++;
vis[a[i].y]++;
vis[a[i].fa]-=;
}
else{
ned=i-;
break;
}
if(i==m)ned=m;
}
dfs3(,,);
if(a[].v-cnt<=x)return ;
else return ;
}
inline int doit(){
int l=,r=a[].v;
while(l<r){
int mid=(l+r)/;
if(check(mid))r=mid;
else l=mid+;
}
return l;
}
int main(){
//freopen("wtf.in","r",stdin);
int size=<<;
char *p=(char*)malloc(size)+size;
__asm__("movl %0,%%esp\n"::"r"(p));
n=read();m=read();
int x,y,v;
for(int i=;i<n;i++){
x=read();y=read();v=read();
init(x,y,v);init(y,x,v);
}tot=;
for(int i=;i<=m;i++){
a[i].x=read();a[i].y=read();
insert(a[i].x,a[i].y,i);
insert(a[i].y,a[i].x,i);
}memset(f,-,sizeof(f));
tarj();
for(int i=;i<=m;i++){
a[i].v=dis[a[i].x]+dis[a[i].y]-dis[a[i].fa]*;
}
sort(a+,a++m,mmp);
printf("%d\n",doit());
return ;
}
树链剖分
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
#define lc x*2
#define rc x*2+1
const int maxn=;
int n,m;
struct nod{
int next,y,v;
}e[maxn*];
int head[maxn]={},tot=;
int dep[maxn]={},fa[maxn]={},kid[maxn]={};
int top[maxn]={};
int dis[maxn]={};
inline void init(int x,int y,int v){
e[++tot].y=y;
e[tot].v=v;
e[tot].next=head[x];
head[x]=tot;
}
int dfs(int x,int pa){
int y,val,v,tsn=,hug=;
dep[x]=dep[pa]+;
fa[x]=pa;
for(int i=head[x];i;i=e[i].next){
y=e[i].y;v=e[i].v;
if(y==pa)continue;
dis[y]=dis[x]+v;
val=dfs(y,x);
if(val>hug)hug=val,kid[x]=y;
tsn+=val;
}
tsn+=;
return tsn;
}
void dfs1(int x,int pa){
int y,v;
top[x]=pa;
if(kid[x])dfs1(kid[x],pa);
for(int i=head[x];i;i=e[i].next){
y=e[i].y;v=e[i].v;
if(y==fa[x]||y==kid[x])continue;
dfs1(y,y);
}
}
int getit(int x,int y){
int xx=top[x],yy=top[y];
while(xx!=yy){
if(dep[xx]<dep[yy]){
swap(xx,yy);
swap(x,y);
}
x=fa[xx];xx=top[x];
}
if(dep[x]>dep[y])return y;
return x;
}
int read(){
char ch=getchar();int x=,f=;
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch<=''&&ch>=''){x*=;x+=ch-'';ch=getchar();}
return x*f;
}
struct wtf{
int x,y,fa,v;
}a[maxn];
bool mmp(wtf aa,wtf bb){
return aa.v>bb.v;
}
int cnt,ned;
int vis[maxn]={};
void dfs3(int x,int val){
int y,v;
for(int i=head[x];i;i=e[i].next){
y=e[i].y;v=e[i].v;
if(y==fa[x])continue;
dfs3(y,v);
vis[x]+=vis[y];
}
if(vis[x]==ned)cnt=max(cnt,val);
}
inline bool check(int x){
cnt=;
memset(vis,,sizeof(vis));
for(int i=;i<=m;i++){
if(a[i].v>x){
vis[a[i].x]++;
vis[a[i].y]++;
vis[a[i].fa]-=;
}
else{
ned=i-;
break;
}
if(i==m)ned=m;
}
dfs3(,);
if(a[].v-cnt<=x)return ;
else return ;
}
inline int doit(){
int l=,r=a[].v;
while(l<r){
int mid=(l+r)/;
if(check(mid))r=mid;
else l=mid+;
}
return l;
}
int main(){
//freopen("wtf.in","r",stdin);
int size=<<;
char *p=(char*)malloc(size)+size;
__asm__("movl %0,%%esp\n"::"r"(p));
n=read();m=read();
int x,y,v;
for(int i=;i<n;i++){
x=read();y=read();v=read();
init(x,y,v);init(y,x,v);
}dfs(,);
dfs1(,);
for(int i=;i<=m;i++){
a[i].x=read();a[i].y=read();
a[i].fa=getit(a[i].x,a[i].y);
a[i].v=dis[a[i].x]+dis[a[i].y]-*dis[a[i].fa];
}sort(a+,a++m,mmp);
printf("%d\n",doit());
return ;
}