洛谷 P2680 运输计划

题目背景

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

题目描述

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的物流公司完成阶段性工作所需要的最短时间。

输入输出样例

输入样例#1：

输出样例#1：

说明

所有测试数据的范围和特点如下表所示

请注意常数因子带来的程序效率上的影响。

这道题很容易就能想到二分答案，因为答案具有单调性。但是……啥？树上差分？？？喵喵喵？？？

树上差分是一种树上的前缀和+延迟思想。还是非常浅显易懂的。可以看看这篇博客：http://blog.csdn.net/zhayan9qvq/article/details/54999472

于是，一篇代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 3e5 + 100;
const int max2 = 18;
int n, m, u, v, w;
struct edge {
	int v, w, next;
}e[maxn << 1];
struct DATA{
	int u, v, lca;
	long long w;
	bool operator < (const DATA &a) const {return w > a.w;}
}pt[maxn];
int head[maxn], cnt;
int tmp[maxn], p[maxn][19], depth[maxn], side[maxn];
long long dis[maxn];

inline void read(int & ret) {
	ret = 0;
	char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
}

inline void read(long long & ret) {
	ret = 0;
	char c = getchar();
	while(c > '9' || c < '0') c = getchar();
	while(c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();
}

inline void adde(const int &u, const int &v, const int &w) {
	e[cnt] = (edge) {v, w, head[u]};
	head[u] = cnt++;
}
void lcadfs(int u, int fa, int w) {
	depth[u] = depth[fa] + 1;
	dis[u] = dis[fa] + w;
	p[u][0] = fa;
	for(register int i = 1; i <= max2; ++i)
		p[u][i] = p[p[u][i-1]][i-1];
	for(register int i = head[u]; ~i; i = e[i].next) {
		int v = e[i].v;
		if(v == fa) continue;
		side[v] = i;
		lcadfs(v, u, e[i].w);
	}
}
int lca(int a, int b) {
	if(depth[a] < depth[b]) swap(a, b);
	for(register int i = max2; i >= 0; --i)
		if(depth[a] - (1 << i) >= depth[b])
			a = p[a][i];
	if(a == b) return a;
	for(register int i = max2; i >= 0; --i)
		if(p[a][i] != p[b][i])
			a = p[a][i], b = p[b][i];
	return p[a][0];
}
int mx, num;
int dfs(int u, int fa) {
	for(register int i = head[u]; ~i; i = e[i].next) {
		int v = e[i].v;
		if(v == fa) continue;
		tmp[u] += dfs(v, u);
	}
	if(num < tmp[u])	num = tmp[u], mx = e[side[u]].w;
	else 	if(num == tmp[u])	mx = max(mx, e[side[u]].w);
	return tmp[u];
}
bool check(long long mid) {
	memset(tmp, 0, sizeof(tmp)); 
	int pos = 1;
	mx = num = 0;
	for(pos = 1; pos <= m && pt[pos].w > mid; ++pos)
		++tmp[pt[pos].u], ++tmp[pt[pos].v], tmp[pt[pos].lca] -= 2;
	dfs(1, 0);
	if(pos == 1) return true;
	return (pos - 1 == num && (pt[1].w - mx <= mid));
}
long long DS(long long l, long long r) {
	while(l + 1 < r) {
		long long mid = (l + r) / 2;
		if(check(mid)) r = mid;
		else l = mid;
	}
	return r;
}

int main() {
	memset(head, -1, sizeof(head));
	read(n), read(m);
	for(register int i = 1; i < n; ++i) {
		read(u), read(v), read(w);
		adde(u, v, w), adde(v, u, w);
	}
	lcadfs(1, 0, 0);
	for(register int i = 1; i <= m; ++i) {
		read(pt[i].u), read(pt[i].v);
		pt[i].lca = lca(pt[i].u, pt[i].v);
		pt[i].w = dis[pt[i].u] + dis[pt[i].v] - (dis[pt[i].lca] << 1);
	}
	sort(pt + 1, pt + m + 1);
	if(m == 0) {printf("0\n");return 0;}
	printf("%lld\n", DS(-1, (long long)1e14 + 1));
	return 0;
}

Rockdu's Blog