记录编号	539512	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	WxjianF019	是否通过	通过
代码语言	C++	运行时间	2.986 s
提交时间	2019-08-07 23:42:49	内存使用	41.12 MiB

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=3e5+5;
int n,m,q[maxn][3],max_dis=0;
vector<int>v[maxn],w[maxn];
int a[maxn],dis[maxn],mark[maxn],fa[maxn],size[maxn],dep[maxn],top[maxn],son[maxn],pos[maxn],cnt;
void Dfs(int rt){
    size[rt]=1;
    for(int i=0;i<v[rt].size();i++){
        int to=v[rt][i];
        if(!size[to]){
            fa[to]=rt;
            dis[to]=dis[rt]+w[rt][i];
            dep[to]=dep[rt]+1;a[to]=w[rt][i];
            Dfs(to);size[rt]+=size[to];
            if(size[to]>size[son[rt]])son[rt]=to;
        }
    }
}
void Dfs(int rt,int tp){
    top[rt]=tp,pos[rt]=++cnt;
    if(son[rt])Dfs(son[rt],tp);
    for(int i=0;i<v[rt].size();i++)
        if(!pos[v[rt][i]])Dfs(v[rt][i],v[rt][i]);
}
int LCA(int x,int y){
    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);
    return x;
}
void MArk(int x,int y){
    if(pos[x]<=pos[y])
    mark[pos[x]]++,mark[pos[y]+1]--;
}
void Mark(int x,int y){
    while(top[x]^top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        MArk(top[x],x);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    if(x!=y)MArk(son[x],y);
}
bool Judge(int mid){
    int tot=0;memset(mark,0,sizeof mark);
    for(int i=0;i<m;i++)if(q[i][2]>mid)tot++,Mark(q[i][0],q[i][1]);
    if(!tot)return true;
    for(int i=2;i<=n;i++)mark[i]+=mark[i-1];
    for(int i=2;i<=n;i++)
        if(mark[pos[i]]==tot&&max_dis-a[i]<=mid)return true;
    return false;
}
int main(){
    freopen("transport.in","r",stdin);freopen("transport.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int x,y,z,i=1;i<n;i++){
        scanf("%d%d%d",&x,&y,&z);
        v[x].push_back(y),w[x].push_back(z);
        v[y].push_back(x),w[y].push_back(z);
    }
    Dfs(1),Dfs(1,1);
    for(int x,y,i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        q[i][0]=x;q[i][1]=y;q[i][2]=dis[x]+dis[y]-2*dis[LCA(x,y)];
        max_dis=max(max_dis,q[i][2]);
    }
    int l=0,r=max_dis;
    while(l<r){
        int mid=l+r>>1;
        if(Judge(mid))r=mid;
        else l=mid+1;
    }
    printf("%d\n",l);
    return 0;
}