记录编号	269331	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	1.232 s
提交时间	2016-06-13 14:31:51	内存使用	38.46 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
inline void read(int &x){
	x=0;char ch;
	while(ch=getchar(),ch<'!');
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
const int maxn = 500010;
struct Edge{
	int to,next,dis;
}G[maxn*2];//
int head[maxn],ecnt;
void add1(int u,int v,int d){
	G[++ecnt].to = v;
	G[ecnt].dis = d;
	G[ecnt].next = head[u];
	head[u] = ecnt;
}
struct Save{
    int s,t;
}cmd[maxn];
int deep[maxn],fa[maxn],siz[maxn],top[maxn],vis[maxn];
//  深度       父亲     节点数  重链顶端节点 访问标记
int dis[maxn],t_w[maxn],son[maxn];//son就不解释了
// 到根的距离 边权压到节点上
void dfs(int u){
	vis[u]=1;
	siz[u]=1;
	for(int i=head[u];i;i=G[i].next){
		int to=G[i].to;
		if(vis[to]) continue;
		fa[to]=u;// 记录父亲 
		deep[to]=deep[u]+1;//深度 
		dis[to]=dis[u]+G[i].dis;//到根节点的距离 
		t_w[to]=G[i].dis;//把边权加到点上 
		dfs(to);
		siz[u]+=siz[to];//子树大小 
		if(siz[son[u]]<siz[to])//找重儿子 
			son[u]=to;
	}
} 
int map[maxn],cnt;
void init(const int &x,const int &y){//计算top,map数组
	top[x] = y;//top一条重链上的顶端
    map[x] = ++cnt;//节点在dfs序上的对应
    if( son[x] != 0 ) init(son[x],y);//应先搜重(zhong)儿子
    for(int i=head[x];i;i=G[i].next){
        if( G[i].to != son[x] && G[i].to != fa[x] ){//重儿子已搜过，不可以搜索父亲
            init(G[i].to,G[i].to);//(出了这一条重链)
        }
    }
}
int lca(int a,int b){
    while(top[a] != top[b]){//不处于同一条重链
        deep[top[a]] < deep[top[b]] ? swap(a,b),1:0;//选择深度大的向上提
        a = fa[ top[a] ];//我提 !!!!
    }
    //此时一定在同一条重链上
    return deep[a] < deep[b] ? a:b;//选择深度小的
}
int T[maxn],n,m;
void add(int s,int t){if(s > t) return;++T[s];--T[t+1];}//O(1)神奇大法
void doo(int x,int y){
    while(top[x] != top[y]){
        deep[top[x]] < deep[top[y]] ? swap(x,y),1:0;
        add(map[ top[x] ],map[x]);//求lca时对边附加信息
        x = fa[ top[x] ];
    }
    deep[x] > deep[y]?  swap(x,y),1:0;
    add(map[ son[x] ] ,map[y]);//附加信息
    return;
}
int ans[maxn],max_f=0;
bool check(int x){
    memset(T,0,sizeof(T));cnt = 0;
    for(int i=1;i<=m;++i){
        if(ans[i] > x ) ++cnt,doo(cmd[i].s,cmd[i].t);//需要虫洞
    }
    if( !cnt ) return true;
    for(int i=2;i<=n;++i) T[i] += T[i-1];//求前缀和O(1)神奇大法 
    for(int i=2;i<=n;++i)
        if(T[map[i]]== cnt && max_f-t_w[i] <= x) return true;
        //在这几条超限边的重合部分，如果改造为虫洞成为可行解，则return true，否则return false；
    return false;
}
int main(){
    freopen("transport.in","r",stdin);
    freopen("transport.out","w",stdout);
	read(n),read(m);
	int u,v,d;
	for(int i=1;i<n;++i){
		read(u),read(v),read(d);
		add1(u,v,d),add1(v,u,d);
	}
	deep[1] = 1;
	dfs(1);
	init(1,1);
    for(int i=1;i<=m;++i){//储存边
        read(cmd[i].s),read(cmd[i].t);
        ans[i] = dis[cmd[i].s] + dis[cmd[i].t] - 2*dis[lca(cmd[i].s,cmd[i].t)];
        max_f = cat_max(max_f,ans[i]);
    }
    int l=0,r=max_f,mid,ret;
    while(l<=r){//二分答案
        mid = (l+r) >> 1;
        if( check(mid) ){
            ret = mid,r = mid-1;
        }else l = mid + 1;
    }
    printf("%d",ret);
    fclose(stdin),fclose(stdout);return 0;
}