【NOIP2015】运输计划
标签： 树上差分 LCA 二分答案
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。
接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j 个运输计划是从 uj 号星球飞往 vj 号星球。
Output
共 1 行,包含 1 个整数,表示小 P 的物流公司完成阶段性工作所需要的最短时间。
Sample Input
6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5
Sample Output
11
Hint
所有测试数据的范围和特点如下表所示
请注意常数因子带来的程序效率上的影响。
题意
给你一棵树，有很多条路径，让你把一条边的边权设为0,使路径的最大值最小。
题解
- 最大值最小，很容易想到二分答案。我们二分答案x,接下来我们只需要判断是否有一条边，使得所有路径在这条边为0的情况下的长度都小于x。
- 如何找这样一条边呢？我们可以把所有路径长大于x的的路径上的边都找出来，然后统计一下。最后对每条边判断一下，是否所有路径都经过它就行了。
- 直接统计肯定是不行的，我们需要用某些数据结构维护一下。很容易想到树剖，虽然可以做，但是在时空及编程复杂度上都不是特别满意。那该怎么办呢？注意到我们是先统计，最后再判断，我们可以使用一个树上差分，就可以在O(n)时间内实现check操作。
- 最后这道题其实还是个卡常题......但是lca我并不会写tarjan。所以运用了一些特殊的卡常技巧,比如说在差分后统计前缀和时不用dfs，而是先把拓扑序求出来，再按拓扑序做。
Code
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define REP(i,a,b) for(register int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
inline int read()
{
int sum=0,p=1;char ch=getchar();
while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
if(ch=='-')p=-1,ch=getchar();
while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
return sum*p;
}
const int maxn=3e5+20;
struct node {
int v,next,w;
};
node e[maxn*2];
int cnt,start[maxn];
int n,m;
int lev[maxn],prevv[maxn];//lev[u]表示root到u的这条链上的边全部加lev[u]，prevv[u]表示u到u父亲的那条边的边权
inline void addedge(int u,int v,int w)
{
e[++cnt]={v,start[u],w};
start[u]=cnt;
}
int deep[maxn],p[maxn][20],dist[maxn];
int tp[maxn];
inline void dfs(int u,int fa)
{
p[u][0]=fa;
EREP(i,u)
{
int v=e[i].v;
if(v==fa)continue;
deep[v]=deep[u]+1;
dist[v]=dist[u]+e[i].w;
prevv[v]=e[i].w;
dfs(v,u);
}
}
inline int Lca(register int u,register int v)
{
if(deep[v]>deep[u])swap(u,v);
DREP(i,19,0)if(deep[p[u][i]]>=deep[v])u=p[u][i];
if(u==v)return u;
DREP(i,19,0)if(p[u][i]!=p[v][i])u=p[u][i],v=p[v][i];
return p[u][0];
}
struct query {
int u,v,lca,dis;
};
bool cmp(const query a,const query b)
{
return a.dis>b.dis;
}
query Q[maxn];
inline void init()
{
n=read();m=read();
REP(i,1,n-1)
{
int u=read(),v=read(),w=read();
addedge(u,v,w);
addedge(v,u,w);
}
deep[1]=1;
dfs(1,-1);
for(int j=1;j<=19;j++)
{
REP(i,1,n)p[i][j]=p[p[i][j-1]][j-1];
}
REP(i,1,m)
{
int u=read(),v=read(),lca,dis;
lca=Lca(u,v);
dis=dist[u]+dist[v]-2*dist[lca];
Q[i]={u,v,lca,dis};
}
sort(Q+1,Q+m+1,cmp);
stack <int> st;
st.push(1);
REP(i,1,n)
{
int u=tp[i]=st.top();st.pop();
EREP(j,u)
{
int v=e[j].v;
if(v!=p[u][0])
st.push(v);
}
}
}
inline bool check(register int x)
{
register int dist=0,cnt=0;
REP(i,1,n)lev[i]=0;
REP(i,1,m)
{
if(Q[i].dis>x)
{
cnt++;
dist=max(dist,Q[i].dis-x);
lev[Q[i].u]++;lev[Q[i].v]++;
lev[Q[i].lca]-=2;
}else break;
}
DREP(i,n,1)lev[p[tp[i]][0]]+=lev[tp[i]];
REP(i,1,n)if(lev[i]==cnt && prevv[i]>=dist)return true;
return false;
}
inline void doing()
{
register int l=0,r=(1<<30);
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l<<endl;
}
int main()
{
init();
doing();
return 0;
}