2109. [NOIP2015] 运输计划

★★★ 输入文件：transport.in 输出文件：transport.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

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

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

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

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

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

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

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

【输入格式】

第一行包括两个正整数 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 的物流公司完成阶段性工作所需要的最短时间。

【样例输入】

【样例输出】

【提示】

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

数据结构(树链剖分)：COGS 2109. [NOIP2015] 运输计划

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

　　哎，拼命优化还是95分。

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int maxn=;

 int n,m;

 int E[maxn][],cnt,fir[maxn],to[maxn<<],nxt[maxn<<],val[maxn<<];

 void addedge(int a,int b,int v){

     nxt[++cnt]=fir[a];to[cnt]=b;fir[a]=cnt;val[cnt]=v;

 }

 int dep[maxn],son[maxn],sz[maxn],fa[maxn],dis[maxn];

 void DFS(int x){

     sz[x]=;

     for(int i=fir[x];i;i=nxt[i])

         if(to[i]!=fa[x]){

             dep[to[i]]=dep[x]+;

             dis[to[i]]=dis[x]+val[i];

             fa[to[i]]=x;

             DFS(to[i]);

             sz[x]+=sz[to[i]];

             if(sz[son[x]]<sz[to[i]])

                 son[x]=to[i];

         }

 }

 int top[maxn],ID[maxn],tot;

 void DFS(int x,int tp){

     ID[x]=++tot;top[x]=tp;

     if(son[x])DFS(son[x],tp);

     for(int i=fir[x];i;i=nxt[i])

         if(!ID[to[i]])

             DFS(to[i],to[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]];

     }

     return dep[x]>dep[y]?y:x;

 }

 int Mx1[maxn*],Mx2[maxn*];

 struct Node{

     int l,r;

     Node(int L=,int R=){

         l=L;r=R;

     }

     bool operator <(const Node &b)const{

         return l<b.l;

     }

 }st[maxn];

 int V[maxn];

 void Update1(int x,int l,int r,int a,int b,int g){

     if(l>=a&&r<=b){

         Mx1[x]=max(Mx1[x],g);

         return;

     }

     int mid=(l+r)>>;

     if(mid>=a)Update1(x<<,l,mid,a,b,g);

     if(mid<b)Update1(x<<|,mid+,r,a,b,g);

 }    

 void Update2(int x,int l,int r,int a,int b,int g){

     if(l>=a&&r<=b){

         Mx2[x]=max(Mx2[x],g);

         return;

     }

     int mid=(l+r)>>;

     if(mid>=a)Update2(x<<,l,mid,a,b,g);

     if(mid<b)Update2(x<<|,mid+,r,a,b,g);

 }

 int Query1(int x,int l,int r,int g){

     if(l==r)

         return Mx1[x];

     int mid=(l+r)>>;

     if(mid>=g)return max(Query1(x<<,l,mid,g),Mx1[x]);

     else return max(Query1(x<<|,mid+,r,g),Mx1[x]);

 }

 int Query2(int x,int l,int r,int g){

     if(l==r)

         return Mx2[x];

     int mid=(l+r)>>;

     if(mid>=g)return max(Query2(x<<,l,mid,g),Mx2[x]);

     else return max(Query2(x<<|,mid+,r,g),Mx2[x]);

 }

 void Solve(int x,int y,int sum){

     int tp=;

     while(top[x]!=top[y]){

         if(dep[top[x]]<dep[top[y]])swap(x,y);

         st[++tp]=Node(ID[top[x]],ID[x]);

         x=fa[top[x]];

     }

     if(dep[x]<dep[y])swap(x,y);

     if(x!=y)st[++tp]=Node(ID[son[y]],ID[x]);

     sort(st,st+tp+);

     for(int i=;i<=tp;i++)

         Update1(,,n,st[i].l,st[i].r,sum);

     int L=;

     for(int i=;i<=tp;i++){

         if(L<=st[i].l-)

             Update2(,,n,L,st[i].l-,sum);

         L=st[i].r+;

     }

     if(L<=n)Update2(,,n,L,n,sum);

 }    

 int main(){

 #ifndef ONLINE_JUDGE

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

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

 #endif

     scanf("%d%d",&n,&m);

     for(int i=;i<n;i++){

         scanf("%d%d%d",&E[i][],&E[i][],&E[i][]);

         addedge(E[i][],E[i][],E[i][]);

         addedge(E[i][],E[i][],E[i][]);

     }

     DFS();

     DFS(,);    

     memset(Mx1,0x80,sizeof(Mx1));

     memset(Mx2,0x80,sizeof(Mx2));

     for(int i=;i<n;i++){

         if(dep[E[i][]]<dep[E[i][]])

             swap(E[i][],E[i][]);

         V[E[i][]]=E[i][];

     }

     int Max=,pa,pb;

     while(m--){

         int a,b,lca;

         scanf("%d%d",&a,&b);

         lca=Lca(a,b);

         if(dis[a]+dis[b]-*dis[lca]>Max){

             pa=a,pb=b;

             Max=dis[a]+dis[b]-*dis[lca];

         }

         Solve(a,b,dis[a]+dis[b]-*dis[lca]);

     }    

     int ans=;

     while(pa!=pb){

         if(dep[pa]<dep[pb])swap(pa,pb);

         int ret=max(Query1(,,n,ID[pa])-V[pa],Query2(,,n,ID[pa]));

         ans=min(ans,ret);

         pa=fa[pa];

     }

     printf("%d\n",ans);

     return ;

 }

秒客网