NOIP2015_提高组Day2_3_运输计划

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<iomanip>

#include<map>

#include<set>

#include<vector>

#include<ctime>

#include<cmath>

#define LL long long

using namespace std;

#define LL long long

#define up(i,j,n) for(int i=(j);(i)<=(n);(i)++)

#define max(x,y) ((x)<(y)?(y):(x))

#define min(x,y) ((x)<(y)?(x):(y))

#define FILE "1"

#define pii pair<int,int>

const int maxn=,inf=;

int read(){

    int x=;bool flag=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')flag=;ch=getchar();}

    while(ch<=''&&ch>=''){x=x*+ch-'';ch=getchar();}

    return flag?-x:x;

}

int n,m;

struct node{

    int y,next,v;

}e[maxn<<];

int linkk[maxn],len=,fa[maxn],w[maxn],dep[maxn],top[maxn],siz[maxn],son[maxn],d[maxn];

void insert(int x,int y,int v){

    e[++len].y=y;

    e[len].v=v;

    e[len].next=linkk[x];

    linkk[x]=len;

}

int q[maxn],tail=,head=;

void dfs(int x){

    siz[x]=;

    for(int i=linkk[x];i;i=e[i].next){

        if(e[i].y==fa[x])continue;

        fa[e[i].y]=x;w[e[i].y]=e[i].v;dep[e[i].y]=dep[x]+;

        dfs(e[i].y);

        siz[x]+=siz[e[i].y];

        if(siz[e[i].y]>siz[son[x]])son[x]=e[i].y;

    }

}

void dfs2(int x){

    if(son[x]){

        top[son[x]]=top[x];

        d[son[x]]=d[x]+w[son[x]];

        dfs2(son[x]);

    }

    for(int i=linkk[x];i;i=e[i].next){

        if(e[i].y==fa[x]||e[i].y==son[x])continue;

        top[e[i].y]=e[i].y;

        d[e[i].y]=;

        dfs2(e[i].y);

    }

}

pii lca(int x,int y){

    int u,v;

    int sum=;

    while(x!=y){

        u=top[x],v=top[y];

        if(u==v)return make_pair((dep[x]>dep[y]?y:x),sum+abs(d[x]-d[y]));

        if(dep[u]>dep[v]){swap(x,y);swap(u,v);}

        sum+=d[y]+w[v];

        y=fa[v];

    }

    return make_pair(x,sum);

}

struct Node{

    int x,y,v,f;

    bool operator<(const Node &b)const{return v>b.v;}

}a[maxn];

int vis[maxn];

int maxx=,flag=;

void Dfs(int x){

    for(int i=linkk[x];i;i=e[i].next){

        if(e[i].y==fa[x])continue;

        Dfs(e[i].y);

        vis[x]+=vis[e[i].y];

    }

    if(vis[x]==flag)maxx=max(maxx,w[x]);

}

int work(int mid){

    memset(vis,,sizeof(vis));

    for(int i=;i<=mid;i++)vis[a[i].x]++,vis[a[i].y]++,vis[a[i].f]-=;//比较暴力的差分

    //可以利用树链剖分将树划分成线段，在上面做差分，常数要比这个小的多，实测结果是#20会超

    maxx=;flag=mid;Dfs();

    return maxx;

}

void slove(){

    n=read();m=read();

    int x,y,v;

    up(i,,n){

        x=read(),y=read(),v=read();

        insert(x,y,v);insert(y,x,v);

    }

    dfs();top[]=;

    dfs2();

    pii temp;

    up(i,,m){

        a[i].x=read(),a[i].y=read();

        temp=lca(a[i].x,a[i].y);

        a[i].v=temp.second;a[i].f=temp.first;

    }

    sort(a+,a+m+);

    int left=,right=m,mid,ans=inf;//也可以1-a[1].v这样枚举，加个记忆化就好；

    while(left<=right){

        mid=(left+right)>>;

        int fee=a[].v-work(mid);

        if(fee>a[mid+].v)right=mid-;

        else left=mid+;

        ans=min(ans,max(fee,a[mid+].v));

    }

    cout<<ans<<endl;

}

int main(){

    freopen(FILE".in","r",stdin);

    freopen(FILE".out","w",stdout);

    slove();

    return ;

}

//如果window下评测注意加个开栈