Luogu运输计划
2017-08-05运输计划
题目描述
L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物
流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。
为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?
输入输出格式
输入格式： 输入文件名为 transport.in。
第一行包括两个正整数 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的物流公司完成阶段性工作所需要的最短时间。
思路
保证了是一棵树，那么求树上距离应该就是lca了（弱鸡只会倍增求lca）
因为是同时开始，所以需要的最短时间是最大值，这是最大值最小，多半就是二分答案了
然后判定上就要GG了2333
对于每一个分出来的答案，可以知道比这个ans小的路径，我们删不删他们的边都是无所谓的；对于大于这个ans的路径，每一条我们都得删一下，否则一定不合法
我们用link[i]表示i到它父亲的边—这条边是唯一的
然后对于每一条不合法的路径，我们可以用树上差分来统计出每一条边经过了多少次（sum[i]）—u++，v++，代表此处以及以上的边都走过，但是他们只走到了lca，所以lca处-=2，代表lca之上的边没有走过，加一个dfs就可以统计出来所有边走过的次数
最后是二分的边界，可以知道最坏的情况是max（路径长），而每一条边的长度最大是1000，所以左边界是max（r-1000,0）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 300010
#define M 300010*2
using namespace std;
int n,m,link[N];
int sum[N],head[N],next[M],to[M],len[M],e;
int ol[N],up[N][25],dis[N],dep[N];
struct ovo
{
int u,v,l,lca;
}a[N];
void buid(int u,int v,int l)
{
next[++e]=head[u],head[u]=e;
to[e]=v,len[e]=l;
}
void dfs(int now,int fa,int tot,int d)
{
up[now][0]=fa;
dis[now]=tot;
dep[now]=d;
for(int i=head[now];i;i=next[i])
{
int j=to[i];
if(j==fa) continue;
link[j]=i;
dfs(j,now,tot+len[i],d+1);
}
}
void do_st()
{
dfs(1,0,0,0);
for(int j=1;j<=20;++j)
{
for(int i=1;i<=n;++i)
{
up[i][j]=up[up[i][j-1]][j-1];
}
}
}
int ask(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
int c=dep[u]-dep[v];
for(int i=0;i<=20;++i)
{
if(c&(1<<i)) u=up[u][i];
}
if(u==v) return u;
for(int i=20;i>=0;--i)
{
if(up[u][i]!=up[v][i])
{
u=up[u][i];
v=up[v][i];
}
}
return up[u][0];
}
bool comp(ovo aa,ovo bb)
{
return aa.l<bb.l;
}
void dfs2(int now,int fa)
{
for(int i=head[now];i;i=next[i])
{
int j=to[i];
if(j==fa) continue;
dfs2(j,now);
sum[now]+=sum[j];
}
}
bool can(int ans)
{
memset(sum,0,sizeof(sum));
int too=lower_bound(ol+1,ol+m+1,ans+1)-ol;
int s=m-too+1;
for(int i=too;i<=m;++i)
{
sum[a[i].u]++;
sum[a[i].v]++;
sum[a[i].lca]-=2;
}
dfs2(1,0);
for(int i=1;i<=n;++i)
{
if(sum[i]==s)
if(ol[m]-len[link[i]]<=ans) return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;++i)
{
int u,v,l;
scanf("%d%d%d",&u,&v,&l);
buid(u,v,l);
buid(v,u,l);
}
do_st();
for(int i=1;i<=m;++i)
{
scanf("%d%d",&a[i].u,&a[i].v);
int lc=ask(a[i].u,a[i].v);
a[i].lca=lc;
ol[i]=a[i].l=dis[a[i].u]+dis[a[i].v]-2*dis[lc];
}
sort(ol+1,ol+m+1);
sort(a+1,a+m+1,comp);
int l=max(ol[m]-1000,0),r=ol[m];
while(l<=r)
{
int mid=(l+r)>>1;
if(can(mid)) r=mid-1;
else l=mid+1;
}
printf("%d",l);
return 0;
}