[NOIP2015] 提高组 洛谷P2680 运输计划

题目背景

公元 2044 年,人类进入了宇宙纪元。

题目描述

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物

流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。

为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。

如果小 P 可以*选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?

输入输出格式

输入格式：

输入文件名为 transport.in。

第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。

接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai, bi 和 ti,表示第

i 条双向航道修建在 ai 与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。

接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j个 运输计划是从 uj 号星球飞往 vj 号星球。

输出格式：

输出 共1行,包含1个整数,表示小P的物流公司完成阶段性工作所需要的最短时间。

输入输出样例

输入样例#1：

6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5

输出样例#1：

11

说明

所有测试数据的范围和特点如下表所示

请注意常数因子带来的程序效率上的影响。

二分答案。

先通过倍增LCA求出每个运输计划消耗的时间。

二分尝试最短时间。统计所需时间大于限定值的运输计划。如果可以通过将它们共用的一条边权值变为0使得它们的用时都小于限定值，则该限定值可行。

 /*by SilverN*/
 #include<algorithm>
 #include<iostream>
 #include<cstring>
 #include<cstdio>
 #include<cmath>
 #include<vector>
 using namespace std;
 const int mxe=;
 const int mxn=;
 int read(){
     int x=,f=;char ch=getchar();
     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
     return x*f;
 }
 struct query{//运输计划
     int x,y;
     int lca,res;
 }c[mxn];
 struct edge{//邻接表
     int v,nxt;
     int dis;
 }e[mxe];
 int hd[mxn],mct=;
 void add_edge(int u,int v,int d){
     e[++mct].v=v;e[mct].dis=d;e[mct].nxt=hd[u];hd[u]=mct;
     return;
 }
 int eid[mxe];//每条边对应的id
 int enode[mxn];//点对应的入边
 int len[mxn];
 //
 int n,m;
 //LCA
 int dep[mxn],dis[mxn];
 int fa[mxn][];
 void DFS(int u,int ff){
     dep[u]=dep[ff]+;
     int i,v;
     for(i=hd[u];i;i=e[i].nxt){
         v=e[i].v;
         if(v==ff)continue;
         fa[v][]=u;
         enode[v]=eid[i];
         dis[v]=dis[u]+e[i].dis;
         DFS(v,u);
     }
     return;
 }
 void LCA_init(){
     int i,j;
     for(i=;i<=;i++)
         for(j=;j<=n;j++)
             fa[j][i]=fa[fa[j][i-]][i-];
     return;
 }
 int LCA(int x,int y){
     if(dep[x]<dep[y])swap(x,y);
     int i;
     for(i=;i>=;--i)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
     if(x==y)return y;
     for(i=;i>=;--i)
         if(fa[x][i]!=fa[y][i]){    x=fa[x][i];y=fa[y][i];}
     return fa[x][];
 }
 //
 inline int dist(int id){
     int x=c[id].x,y=c[id].y;
     int lca=LCA(x,y);
     c[id].lca=lca;
     return (long long)dis[x]+dis[y]-*dis[lca];
 }
 //
 int mxdis=;
 int uct[mxn];
 void ust_count(int u,int ff){//统计每条边的使用次数
     for(int i=hd[u];i;i=e[i].nxt){
         int v=e[i].v;
         if(v==ff)continue;
         ust_count(v,u);
         uct[enode[u]]+=uct[enode[v]];
     }
     return;
 }
 int ege[mxn],cnt=;//存需要时间大于二分答案的运输计划
 bool clc(int x){
     memset(uct,,sizeof uct);
     cnt=;
     for(register int i=;i<n;++i){
         if(c[i].res>x)ege[++cnt]=i;
     }
     for(register int i=;i<=cnt;++i){
         ++uct[enode[c[ege[i]].x]];
         ++uct[enode[c[ege[i]].y]];
         uct[enode[c[ege[i]].lca]]-=;
     }
     ust_count(,);
     for(register int i=;i<n;++i){
 //        printf("uct:%d  len:%d\n",uct[i],len[i]);
         if(uct[i]==cnt && len[i]>=mxdis-x)return true;
     }
     return false;
 }

 //
 int main(){
     int i,j;
     n=read();m=read();
     if (n==){printf("");return ;}
     int u,v,d;
     int smm=;
     for(register int i=;i<n;++i){
         u=read();v=read();d=read();
         add_edge(u,v,d);eid[mct]=i;
         add_edge(v,u,d);eid[mct]=i;
         len[i]=d;
         smm+=d;
     }
     dep[]=;dis[]=;
     DFS(,);
     LCA_init();
     //init
     for(register int i=;i<=m;++i){
         c[i].x=read();c[i].y=read();
         c[i].res=dist(i);
         mxdis=max(mxdis,c[i].res);
     }
     int l=,r=smm,ans=;
     while(l<=r){
         int mid=(l+r)>>;
         if(clc(mid))ans=mid,r=mid-;
         else l=mid+;
     }
     printf("%d\n",ans);
     return ;
 }