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

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 的物流公司完成阶段性工作所需要的最短时间。

【样例输入】

【样例输出】

【提示】

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

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

　　哎，拼命优化还是95分。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 using namespace std;
  6 const int maxn=300010;
  7 
  8 int n,m;
  9 int E[maxn][3],cnt,fir[maxn],to[maxn<<1],nxt[maxn<<1],val[maxn<<1];
 10 void addedge(int a,int b,int v){
 11     nxt[++cnt]=fir[a];to[cnt]=b;fir[a]=cnt;val[cnt]=v;
 12 }
 13 
 14 int dep[maxn],son[maxn],sz[maxn],fa[maxn],dis[maxn];
 15 
 16 void DFS(int x){
 17     sz[x]=1;
 18     for(int i=fir[x];i;i=nxt[i])
 19         if(to[i]!=fa[x]){
 20             dep[to[i]]=dep[x]+1;
 21             dis[to[i]]=dis[x]+val[i];
 22             fa[to[i]]=x;
 23             DFS(to[i]);
 24             sz[x]+=sz[to[i]];
 25             if(sz[son[x]]<sz[to[i]])
 26                 son[x]=to[i];
 27         }    
 28 }
 29 
 30 int top[maxn],ID[maxn],tot;
 31 void DFS(int x,int tp){
 32     ID[x]=++tot;top[x]=tp;
 33     if(son[x])DFS(son[x],tp);
 34     for(int i=fir[x];i;i=nxt[i])
 35         if(!ID[to[i]])
 36             DFS(to[i],to[i]);
 37 }
 38 
 39 int Lca(int x,int y){
 40     while(top[x]!=top[y]){
 41         if(dep[top[x]]<dep[top[y]])swap(x,y);
 42         x=fa[top[x]];
 43     }
 44     return dep[x]>dep[y]?y:x;
 45 }
 46 
 47 int Mx1[maxn*45],Mx2[maxn*45];
 48 struct Node{
 49     int l,r;
 50     Node(int L=0,int R=0){
 51         l=L;r=R;
 52     }
 53     bool operator <(const Node &b)const{
 54         return l<b.l;
 55     }
 56 }st[maxn];
 57     
 58 
 59     
 60 int V[maxn];
 61 void Update1(int x,int l,int r,int a,int b,int g){
 62     if(l>=a&&r<=b){
 63         Mx1[x]=max(Mx1[x],g);
 64         return;
 65     }
 66     int mid=(l+r)>>1;
 67     if(mid>=a)Update1(x<<1,l,mid,a,b,g);
 68     if(mid<b)Update1(x<<1|1,mid+1,r,a,b,g);
 69 }    
 70     
 71 void Update2(int x,int l,int r,int a,int b,int g){
 72     if(l>=a&&r<=b){
 73         Mx2[x]=max(Mx2[x],g);
 74         return;
 75     }
 76     int mid=(l+r)>>1;
 77     if(mid>=a)Update2(x<<1,l,mid,a,b,g);
 78     if(mid<b)Update2(x<<1|1,mid+1,r,a,b,g);
 79 }
 80     
 81 int Query1(int x,int l,int r,int g){
 82     if(l==r)
 83         return Mx1[x];
 84     int mid=(l+r)>>1;
 85     if(mid>=g)return max(Query1(x<<1,l,mid,g),Mx1[x]);
 86     else return max(Query1(x<<1|1,mid+1,r,g),Mx1[x]);    
 87 }
 88 
 89 int Query2(int x,int l,int r,int g){
 90     if(l==r)
 91         return Mx2[x];
 92     int mid=(l+r)>>1;
 93     if(mid>=g)return max(Query2(x<<1,l,mid,g),Mx2[x]);
 94     else return max(Query2(x<<1|1,mid+1,r,g),Mx2[x]);    
 95 }
 96 void Solve(int x,int y,int sum){
 97     int tp=0;
 98     while(top[x]!=top[y]){
 99         if(dep[top[x]]<dep[top[y]])swap(x,y);
100         st[++tp]=Node(ID[top[x]],ID[x]);
101         x=fa[top[x]];
102     }
103     if(dep[x]<dep[y])swap(x,y);
104     if(x!=y)st[++tp]=Node(ID[son[y]],ID[x]);
105     sort(st,st+tp+1);
106     for(int i=1;i<=tp;i++)
107         Update1(1,1,n,st[i].l,st[i].r,sum);
108     
109     int L=1;
110     for(int i=1;i<=tp;i++){
111         if(L<=st[i].l-1)
112             Update2(1,1,n,L,st[i].l-1,sum);
113         L=st[i].r+1;    
114     }    
115     if(L<=n)Update2(1,1,n,L,n,sum);
116 }    
117     
118 int main(){
119 #ifndef ONLINE_JUDGE
120     freopen("transport.in","r",stdin);
121     freopen("transport.out","w",stdout);
122 #endif
123     scanf("%d%d",&n,&m);
124     for(int i=1;i<n;i++){
125         scanf("%d%d%d",&E[i][0],&E[i][1],&E[i][2]);
126         addedge(E[i][0],E[i][1],E[i][2]);
127         addedge(E[i][1],E[i][0],E[i][2]);
128     }
129     
130     DFS(1);
131     DFS(1,1);    
132     
133     memset(Mx1,0x80,sizeof(Mx1));
134     memset(Mx2,0x80,sizeof(Mx2));
135     
136     for(int i=1;i<n;i++){
137         if(dep[E[i][0]]<dep[E[i][1]])
138             swap(E[i][0],E[i][1]);
139         V[E[i][0]]=E[i][2];
140     }
141     
142     int Max=0,pa,pb;
143     while(m--){
144         int a,b,lca;
145         scanf("%d%d",&a,&b);
146         lca=Lca(a,b);
147         if(dis[a]+dis[b]-2*dis[lca]>Max){
148             pa=a,pb=b;
149             Max=dis[a]+dis[b]-2*dis[lca];
150         }
151         Solve(a,b,dis[a]+dis[b]-2*dis[lca]);
152     }    
153     
154     int ans=233333333;
155     while(pa!=pb){
156         if(dep[pa]<dep[pb])swap(pa,pb);
157         int ret=max(Query1(1,1,n,ID[pa])-V[pa],Query2(1,1,n,ID[pa]));
158         ans=min(ans,ret);
159         pa=fa[pa];
160     }
161     
162     printf("%d
",ans);
163     return 0;
164 }

尽最大的努力，做最好的自己！