记录编号	414943	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.911 s
提交时间	2017-06-15 11:53:40	内存使用	25.50 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9'){
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum;
}
int n,m;
struct edge{
    int s,e,n,w;
}a[600001];
int pre[300001],tot;
inline void init(int s,int e,int w){
    a[++tot].s=s;
    a[tot].e=e;
    a[tot].w=w;
    a[tot].n=pre[s];
    pre[s]=tot;
}
int v[300001],dist[300001];
int size[300001],son[300001],fa[300001],dep[300001];
inline void dfs1(int u){
    size[u]=1;
    son[u]=0;
    for(int i=pre[u];i!=-1;i=a[i].n){
        int e(a[i].e);
        if(e!=fa[u]){
            fa[e]=u;
            dist[e]=dist[u]+a[i].w;
            v[e]=a[i].w;
            dep[e]=dep[u]+1;
            dfs1(e);
            size[u]+=size[e];
            if(size[e]>size[son[u]])
                son[u]=e;
        }
    }
}
int cnt;
int id[300001],pos[300001],top[300001];
inline void dfs2(int u,int rt){
    top[u]=rt;
    id[u]=++cnt;
    pos[cnt]=u;
    if(son[u])
        dfs2(son[u],rt);
    for(int i=pre[u];i!=-1;i=a[i].n){
        int e(a[i].e);
        if(e!=fa[u]&&e!=son[u])
            dfs2(e,e);
    }
}
int dis[300001];
int ggl[300001],ggr[300001];
inline void swp(int &a,int &b){
    a^=b;
    b^=a;
    a^=b;
}
inline int lca(int a,int b){
    while(top[a]!=top[b]){
        if(dep[top[a]]<dep[top[b]])
            swp(a,b);
        a=fa[top[a]];
    }
    return dep[a]<dep[b]?a:b;
}
inline int my_max(int a,int b){
    return a>b?a:b;
}
int m_d;
int mark[300001];
inline void M(int l,int r){
    if(l>r)
        return;
    mark[l]++;
    mark[r+1]--;
}
inline void S(int a,int b){
    while(top[a]!=top[b]){
        if(dep[top[a]]<dep[top[b]])
            swp(a,b);
        M(id[top[a]],id[a]);
        a=fa[top[a]];
    }
    if(dep[a]<dep[b])
        swp(a,b);
    M(id[son[b]],id[a]);
}
inline bool check(int x){
    memset(mark,0,sizeof(mark));
    int gg=0;
    for(int i=1;i<=m;i++)
        if(dis[i]>x){
            gg++;
            S(ggl[i],ggr[i]);
        }
    if(!gg)
        return true;
    for(int i=1;i<=n;i++)
        mark[i]+=mark[i-1];
    for(int i=2;i<=n;i++)
        if(mark[id[i]]==gg&&m_d-v[i]<=x)
            return true;
    return false;
}
inline void write(int x){
	if(x==0){
		putchar('0');
		return;
	}if(x<0)
		putchar('-'),x=-x;
	int len=0,buf[15];
	while(x)
		buf[len++]=x%10,x/=10;
	for(int i=len-1;i>=0;i--)
		putchar(buf[i]+'0');
	return;
}
int main(){
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
    memset(pre,-1,sizeof(pre));
    n=read();
    m=read();
    for(int i=1;i<n;i++){
        int x(read());
        int y(read());
        int z(read());
        init(x,y,z);
        init(y,x,z);
    }
    dfs1(1);
    dfs2(1,1);
    int l(0),r(0);
    for(int i=1;i<=m;i++){
        ggl[i]=read();
        ggr[i]=read();
        dis[i]=dist[ggl[i]]+dist[ggr[i]]-(dist[lca(ggl[i],ggr[i])]<<1);
        r=my_max(r,dis[i]);
        m_d=r;
    }
    while(l<=r){
        int mid((l+r)>>1);
        if(check(mid))
            r=mid-1;
        else
            l=mid+1;
    }
    if(check(r))
		write(r);
    else
        write(l);
    //while(1);
}