4326: NOIP2015 运输计划
Time Limit: 30 Sec Memory Limit: 128 MB
Submit: 886 Solved: 574
[Submit][Status][Discuss]
Description
公元 2044 年，人类进入了宇宙纪元。L 国有 n 个星球，还有 n−1 条双向航道，每条航道建立在两个星球之间，这 n−1 条航道连通了 L 国的所有星球。小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 j，任意飞船驶过它所花费的时间为 tj，并且任意两艘飞船之间不会产生任何干扰。为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后，这 m 个运输计划会同时开始，所有飞船一起出发。当这 m 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。如果小 P 可以*选择将哪一条航道改造成虫洞， 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？
Input
第一行包括两个正整数 n,m，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 1 到 n 编号。接下来 n−1 行描述航道的建设情况，其中第 i 行包含三个整数 ai,bi 和 ti，表示第 i 条双向航道修建在 ai 与 bi 两个星球之间，任意飞船驶过它所花费的时间为 ti。数据保证 1≤ai,bi≤n 且 0≤ti≤1000。接下来 m 行描述运输计划的情况，其中第 j 行包含两个正整数 uj 和 vj，表示第 j 个运输计划是从 uj 号星球飞往 vj号星球。数据保证 1≤ui,vi≤n
Output
输出文件只包含一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。
Sample Input
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
Sample Output
HINT
题解：
※整体思路：=-=明显的lca问题。对于此题，先树链剖分预处理所有计划的lca和计划用时，之后二分答案，用jud函数检验答案是否可行，最后输出最小值。
※jud函数：用树上差分。
如果要对一段连续区间 [a,b)[a,b) 同时加上一个值，只需在开始处加上这个值，在结束后减去这个值，维护前缀和就行了。看上去应该是这样的：
图片来自blog.sengxian.com:
若初始都是 00，让连续区间 [a,b)[a,b) 同时加上一个值 mm 之后，前缀和 Si=∑i0viSi=∑0ivi 即为元素 ii 的值(而其实对每个点i求1~i的前缀和即可求出它的实际值)。下面是前缀和：
如果有多组加减，也不会冲突。
同样的，在树上，我们用 sisi 来表示顶点 ii 到其父亲的这条边被经过的次数，vivi 用于记录顶点信息。
对于每个点对 (a,b)(a,b)，我们将 va+1,vb+1,vLCA(a,b)−2va+1,vb+1,vLCA(a,b)−2。
则树上前缀和 si=∑k∈son(i)vksi=∑k∈son(i)vk。
利用 dfsdfs 序，对于每个点更新它的父亲的 ss 值，前缀和可以在 O(n)O(n) 的时间内算出来。这样，每条边经过的次数就顺利计算出来了。
这个方法的复杂度是线性的，为 O(m+n)O(m+n)。
程序如下：
| 1680299 | ksq2013 | 4326 | Accepted | 31448 kb | 3644 ms | C++/Edit | 2967 B | 2016-10-28 12:02:12 |
#include<bits/stdc++.h>
#define MAXN 310000
namespace F{
const int MAXBUF=<<;
inline char flow(){
static char B[MAXBUF],*S=B,*T=B;
if(S==T){
T=(S=B)+fread(B,,MAXBUF,stdin);
if(S==T)return ;
}
return *S++;
}
inline int read(){
static int x;
static char c;
for(;!isdigit(c=flow()););
for(x=c-;isdigit(c=flow());x=(x<<)+(x<<)+c-);
return x;
}
};
struct Pointer{int v,w;Pointer *nxt;}*fst[MAXN];
struct Plan{int u,v,lca,cost;}plan[MAXN];
inline void link(int u,int v,int w){
static Pointer mem[MAXN<<],*tot=mem;
*++tot=(Pointer){v,w,fst[u]},fst[u]=tot;
*++tot=(Pointer){u,w,fst[v]},fst[v]=tot;
}
int N,M,sz[MAXN],fa[MAXN],son[MAXN],top[MAXN],id[MAXN],d[MAXN],dep[MAXN],bin_var,s[MAXN];
void dfs_init(int x){
sz[x]=;
for(Pointer *j=fst[x];j;j=j->nxt)
if(j->v^fa[x]){
fa[j->v]=x;
d[j->v]=d[x]+j->w;
dep[j->v]=dep[x]+;
dfs_init(j->v);
sz[x]+=sz[j->v];
son[x]=sz[j->v]>sz[son[x]]?j->v:son[x];
}
}
void dfs_make(int x){
top[x]=(x==son[fa[x]])?top[fa[x]]:x;
static int ind;
id[++ind]=x;
if(son[x])dfs_make(son[x]);
for(Pointer *j=fst[x];j;j=j->nxt)
if(j->v^fa[x]&&j->v^son[x])
dfs_make(j->v);
}
inline int dis(int x,int y,int z)
{return d[x]+d[y]-(d[z]<<);}
inline int lca(int x,int y){
while(top[x]^top[y])
dep[top[x]]>dep[top[y]]?
x=fa[top[x]]:
y=fa[top[y]];
return dep[x]<dep[y]?x:y;
}
inline bool jud(int t){
int mxt=,sum=,ans=;
memset(s,,sizeof(s));
for(int i=;i<=M;i++){
if(plan[i].cost<=t)continue;
sum++;
s[plan[i].u]++,s[plan[i].v]++,s[plan[i].lca]-=;
if(plan[i].cost-t>mxt)
mxt=plan[i].cost-t;
}
for(int i=N;i>=;i--)
s[fa[id[i]]]+=s[id[i]];
for(int i=;i<=N;i++)
if((!(s[i]^sum))&&d[i]-d[fa[i]]>ans)
ans=d[i]-d[fa[i]];
return mxt<=ans;
}
void bin_search(){
int l,r,mid;
for(l=-,r=bin_var,mid;r-l>;){
mid=l+r>>;
jud(mid)?r=mid:l=mid;
}
printf("%d\n",r);
}
int main(){
using namespace F;
N=read(),M=read();
for(int i=,u,v,w;i<N;i++)
u=read(),v=read(),w=read(),link(u,v,w);
dfs_init();
dfs_make();
for(int i=,u,v;i<=M;i++){
u=read(),v=read();
plan[i]=(Plan){u,v};
plan[i].lca=lca(plan[i].u,plan[i].v);
plan[i].cost=dis(plan[i].u,plan[i].v,plan[i].lca);
if(plan[i].cost>bin_var)bin_var=plan[i].cost;
}
bin_search();
return ;
}