【NOIP 2015】运输计划

思路

此题做法：二分答案 + LCA + 树上差分。

我们很容易想到二分答案，毕竟答案满足单调性且较难直接计算。那么我们需要的就是一个 check 函数。我们的重点就在 check 函数上。

我们现在已知我们二分出的答案 (x)。我们要判断是否可行。首先，我们先把所有运输计划的两点之间的距离大于 (x) 的找出来，时间复杂度 (O(m))。然后我们需要对这些找出来的边上经过的点标记一下。如果有 (num) 个询问的长度大于 (x)，我们再找到被标记次数为 (num) 的所有边即可。为什么这样做？我们这是为了找出最优的虫洞，能让这些边减小量最大。因为这 (num) 条边的长度都超过了 (x)。所以我们一定要找出这 (num) 个询问都经过的边才行，找出最大值，和 (num) 条边中长度最大的比较一下即可。思路十分清晰，我们只需要用边差分的方式优化一下即可，复杂度为 (O(m))。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
struct edge {
	int to,nxt,w;
} e[N<<1];
int cnt,head[N];
inline void add(int u,int v,int w) {
	e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt,e[cnt].w=w;
}
int f[N][32],dep[N],dis[N];
void build(int u,int fa) {
	dep[u]=dep[fa]+1,f[u][0]=fa;
	for(int i=1; (1<<i)<=dep[u]; i++) {
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int i=head[u]; i; i=e[i].nxt) {
		int v=e[i].to;
		if(v==fa) {
			continue;
		}
		dis[v]=dis[u]+e[i].w,build(v,u);
	}
}
int lca(int x,int y) {
	if(dep[x]<dep[y]) {
		swap(x,y);
	}
	for(int i=30; i>=0; i--) {
		if(dep[f[x][i]]>=dep[y]) {
			x=f[x][i];
		}
		if(x==y) {
			return x;
		}
	}
	for(int i=30; i>=0; i--) {
		if(f[x][i]^f[y][i]) {
			x=f[x][i],y=f[y][i];
		}
	}
	return f[x][0];
}
int n,m,c[N],num,maxn;
struct query {
	int x,y,lca,d;
} a[N];
void dfs(int u,int fa,int val) {
	for(int i=head[u]; i; i=e[i].nxt) {
		int v=e[i].to,w=e[i].w;
		if(v^fa) {
			dfs(v,u,w),c[u]+=c[v];
		}
	}
	if(c[u]==num) {
		maxn=max(maxn,val);
	}
}
bool check(int x) {
	memset(c,0,sizeof(c)),maxn=num=0;
	int need=0;
	for(int i=1; i<=m; i++) {
		if(a[i].d>x) {
			need=max(need,a[i].d-x),c[a[i].x]++,c[a[i].y]++,c[a[i].lca]-=2,num++;
		}
	}
	dfs(1,0,0);
	return need<=maxn;
}
int main() {
	scanf("%d %d",&n,&m);
	for(int i=1,u,v,w; i<n; i++) {
		scanf("%d %d %d",&u,&v,&w),add(u,v,w),add(v,u,w);
	}
	build(1,0);
	for(int i=1; i<=m; i++) {
		scanf("%d %d",&a[i].x,&a[i].y);
		a[i].lca=lca(a[i].x,a[i].y);
		a[i].d=dis[a[i].x]+dis[a[i].y]-2*dis[a[i].lca];
	}
	int l=0,r=1<<30;
	while(l<r) {
		int mid=(l+r)>>1;
		if(check(mid)) {
			r=mid;
		} else {
			l=mid+1;
		}
	}
	printf("%d",l);
	return 0;
}

参考资料

[NOIP-2015] 运输计划 - huayucaiji