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 的物流公司完成阶段性工作所需要的最短时间。
【样例输入】
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
【样例输出】
11
【提示】
所有测试数据的范围和特点如下表所示
请注意常数因子带来的程序效率上的影响。
哎，拼命优化还是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 ;
}