题解 | 运输计划-NOIP2015提高组复赛C题

题目描述

公元 2044 年，人类进入了宇宙纪元。

L 国有 n 个星球，还有 n-1 条双向航道，每条航道建立在两个星球之间，这 n-1 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 u_i 号星球沿最快的宇航路径飞行到 v_i 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 j，任意飞船驶过它所花费的时间为 t_j，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新，L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后，这 m 个运输计划会同时开始，所有飞船一起出发。当这 m 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞，试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？

输入描述:

第一行包括两个正整数n、m，表示L国中星球的数量及小P公司预接的运输计划的数量，星球从1到n编号。

接下来 n-1 行描述航道的建设情况，其中第 i 行包含三个整数 a_i, b_i 和 t_i，表示第i 条双向航道修建在a_i 与b_i 两个星球之间，任意飞船驶过它所花费的时间为t_i。
接下来m 行描述运输计划的情况，其中第j 行包含两个正整数u_j 和 v_j，表示第 j 个运输计划是从 u_j 号星球飞往v_j 号星球。

输出描述:

共 1 行，包含1个整数，表示小P的物流公司完成阶段性工作所需要的最短时间。

示例1

输入

6 3
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5

输出

11

说明

将第1条航道改造成虫洞：则三个计划耗时分别为：11、12、11，故需要花费的时间为12。
将第2条航道改造成虫洞：则三个计划耗时分别为：7、15、11，故需要花费的时间为15。
将第3条航道改造成虫洞：则三个计划耗时分别为：4、8、11，故需要花费的时间为11。
将第4条航道改造成虫洞：则三个计划耗时分别为：11、15、5，故需要花费的时间为15。
将第5条航道改造成虫洞：则三个计划耗时分别为：11、10、6，故需要花费的时间为11。
故将第 3 条或第 5 条航道改造成虫洞均可使得完成阶段性工作的耗时最短，需要花费的时间为 11。

备注

解答

这是一棵树上距离的问题

解答分两个部分：

1、求出给出各点对之间的距离

2、将一条边权减为0使得最大距离最小

树上距离一看就自然想到了【树链剖分+树状数组（或线段树）】，先树剖给点编号，然后套用树状数组结合LCA的算法求出点对距离，1问秒掉

关键是第二问，如何删。

容易想到要选的边一定在最长的路径上，但选最长路径上最长的边不一定是对的，因为第二长的边可能与第一长的边有公共边且不相差多少，但是删去了一个非公共边就错了。

看到最大最小，自然想到二分答案：

我们二分虫洞后最长的边的长度，对于每一个check(m),只需枚举所有比m大的路径，这些路径都得缩短，将这k条路径上每一条边+1，这样一来加到了k的那些边就是所有边的公共边，再看一看他们能不能通过减为0而使这k条边都小于m。

具体怎么维护每条边加了几次，用线段树？

这样二分nlognlogn的复杂度，还是不太放心

鉴于所有的询问都是单点且都在修改之后，我们可以用差分数组以O(n)的总复杂度求出

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lbt(x) (x&-x)
using namespace std;
const int maxn=300005,INF=2000000000;

inline int read(){
	int out=0,flag=1;char c=getchar();
	while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
	while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}
	return out*flag;
}

int N,M,root,rtm=INF,Maxw;
//这块是存边【链式前向星】
int head[maxn],nedge=0;
struct EDGE{
	int to,w,next;
}edge[2*maxn];

inline void build(int a,int b,int w){
	edge[nedge]=(EDGE){b,w,head[a]};
	head[a]=nedge++;
	edge[nedge]=(EDGE){a,w,head[b]};
	head[b]=nedge++;
}

struct node{
	int a,b,w;
}p[maxn];

inline bool operator <(const node& a,const node& b){
	return a.w>b.w;
}
//这块求重心
int Siz[maxn];
void dfs(int u,int f){
	int to,Max=-1,Min=INF;
	Siz[u]=1;
	for(int k=head[u];k!=-1;k=edge[k].next)
		if((to=edge[k].to)!=f){
			dfs(to,u);
			Siz[u]+=Siz[to];
			if(Siz[to]>Max) Max=Siz[to];
			else if(Siz[to]<Min) Min=Siz[to];
		}
	if(N-Siz[u]>Max) Max=N-Siz[u];
	else if(N-Siz[u]<Min) Min=N-Siz[u];
	if(Max!=-1&&Min!=INF&&Max-Min<rtm){
		root=u;
		rtm=Max-Min;
	}
}
//这块是树链剖分
int top[maxn],siz[maxn],fa[maxn],son[maxn],id[maxn],Hash[maxn],dep[maxn],V[maxn],cnt=0;

void dfs1(int u,int f,int d){
	int to;
	siz[u]=1;fa[u]=f;dep[u]=++d;
	for(int k=head[u];k!=-1;k=edge[k].next)
		if((to=edge[k].to)!=f){
			dfs1(to,u,d);
			V[to]=edge[k].w;
			siz[u]+=siz[to];
			if(!son[u]||siz[son[u]]<siz[to]) son[u]=to;
		}
}

void dfs2(int u,int flag){
	int to;
	id[u]=++cnt;Hash[cnt]=u;
	flag ? top[u]=top[fa[u]]:top[u]=u;
	if(son[u]) dfs2(son[u],1);
	for(int k=head[u];k!=-1;k=edge[k].next)
		if((to=edge[k].to)!=son[u]&&to!=fa[u])
			dfs2(to,0);
}
//这块是树状数组
int A[maxn];

inline void add(int u,int v){while(u<=N){A[u]+=v;u+=lbt(u);}}

inline int Sum(int u){int ans=0;while(u>0){ans+=A[u];u-=lbt(u);}return ans;}

inline int Query(int l,int r){return Sum(r)-Sum(l-1);}

inline void init(){for(int i=1;i<=N;i++) add(id[i],V[i]);}

int solve(int u,int v){        //求路径长
	int ans=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ans+=Query(id[top[u]],id[u]);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	return ans+Query(id[u]+1,id[v]);
}

int D[maxn];   //差分数组

inline void update(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) u^=v^=u^=v;
		D[id[top[u]]]+=1;
		D[id[u]+1]-=1;
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) u^=v^=u^=v;
	D[id[u]+1]+=1;
	D[id[v]+1]-=1;
}

bool check(int m){
	int tot=0,v=0;
	while(p[tot+1].w>m){
		++tot;
		update(p[tot].a,p[tot].b);
	}
	for(int i=1;i<=N;i++){
		v+=D[i];D[i]=0;
		if(v==tot&&Maxw-V[Hash[i]]<=m){
			for(int j=i+1;j<=N;j++) D[j]=0;
			return true;
		}
	}
	return false;
}

int main()
{
	fill(head,head+maxn,-1);
	N=read();
	M=read();
	int a,b,w,L=0,R=0;
	for(int i=1;i<N;i++){
		a=read();
		b=read();
		w=read();
		build(a,b,w);
	}
	dfs(1,0);     //求出重心作为根
	dfs1(root,0,0);  //dfs1、dfs2树链剖分
	dfs2(root,0);
	init();      //初始化树状数组
	for(int i=1;i<=M;i++){
		p[i].a=read();
		p[i].b=read();
		p[i].w=solve(p[i].a,p[i].b);
		if(p[i].w>R) R=p[i].w;
	}
	sort(p+1,p+1+M);  //路径排个序
	Maxw=R;
	while(L<R){   //二分答案
		int mid=(L+R)>>1;
		if(check(mid)) R=mid;
		else L=mid+1;
	}
	cout<<L<<endl;
	return 0;
}

来源：Mychael