【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;

}

巴特西

【NOIP2015】运输计划

【NOIP2015】运输计划

Description

题意

题解

Code

最新文章

热门文章