NOIP2015 运输计划

退役选手114514分钟没写博客了

题目

L 国有 \(n\) 个星球，有 \(n-1\) 条双向航道连通了 L 国的所有星球，每条航道连通两个星球，第 \(i\) 条航道通过的时间为 \(t-i\)。

小 P 掌管的物流公司有 \(m\) 个运输计划，每个运输计划形如：有一艘物流飞船需要从 \(u-i\) 号星球沿最快的路径到 \(v-i\) 号星球去。注意：任意两艘飞船之间不会产生任何干扰。

在运输计划开始前，小 P 可以自由选择一条航道改造成虫洞，飞船驶过虫洞不消耗时间。在虫洞建设完成后，这 \(m\) 个运输计划会同时开始，所有飞船一起出发。当这 \(m\) 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。求出小 P 的物流公司完成阶段性工作所需要的最短时间。

数据范围：\(n,m\le 3\times 10^5\)，\(0\le t-i\le 1000\)

分析

一开始没注意到是一棵树，感觉很不可做。

看了下别人题解，才发现这个性质。

所以可以先预处理出每个任务的长度。

之后二分答案，把所有长度\(\geq mid\)的计划数量（记为\(cnt\)）以及该计划经过的边记录一下。

怎么判断是否可以把某条边变成虫洞以满足要求呢？

这个比较简单，如果某条边被每个大于\(mid\)的计划经过，并且删除这个边后，满足\(max\-len-w\leq mid\)，即符合条件。

对于打标记，容易想到树剖。

但是我看了Siyuan大佬博客后，学到了一个比较妙的差分方法。

树上差分后可以按\(dfn\)序算前缀和，这样保证每个点的子树都已经更新到了它上面。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 300005, M = 22;
int head[N], ecnt, n, m, k, dis[N], dep[N], s[N], t[N], L[N], fa[N][M], rnk[N], dfs-clock, len[N], d[N], fr[N];
struct E {int nxt, v, w;} e[N << 1];
void add-edge(int u, int v, int w) {
    e[++ecnt] = {head[u], v, w}; head[u] = ecnt;
    e[++ecnt] = {head[v], u, w}; head[v] = ecnt;
} 

void dfs(int u, int f) {
    fa[u][0] = f;
    rnk[++dfs-clock] = u;
    for (int i = 1; i < M; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (int i = head[u]; i; i = e[i].nxt) {
    	int v = e[i].v, w = e[i].w;
    	if (v == f) continue;
    	dis[v] = dis[u] + w;
    	fr[v] = w;
    	dep[v] = dep[u] + 1;
    	dfs(v, u); 
    }
}
int LCA(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = M - 1; i + 1; i--) {
		if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
	}
	if (u == v) return v;
	for (int i = M - 1; i + 1; i--) {
		if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	}
	return fa[u][0];
}
bool check(int x) {
	memset(d, 0, sizeof d);
	int mx = 0, cnt = 0;
	for (int i = 1; i <= m; i++) {
		if (len[i] <= x) continue;
		cnt++;
		mx = max(len[i], mx);
		d[s[i]]++;
		d[t[i]]++;
		d[L[i]] -= 2;
	}
	for (int i = n; i; i--) {
		int now = rnk[i];
        d[fa[now][0]] += d[now];
        if (d[now] == cnt && mx - fr[now] <= x) return 1;
	}
	return 0;
}

int main() {
	int l = 0, r = 0, ans = 0;
    scanf("%d %d", &n, &m);
    for (int i = 1; i < n; i++) {
    	int u, v, w;
    	scanf("%d %d %d", &u, &v, &w);
    	add-edge(u, v, w);
    }
    dfs(1, 0);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &s[i], &t[i]);
        L[i] = LCA(s[i], t[i]);
        len[i] = dis[s[i]] + dis[t[i]] - 2 * dis[L[i]];
        r = max(len[i], r);
    }
    while (l <= r) {
    	int mid = (l + r) >> 1;
    	if (check(mid)) r = mid - 1, ans = mid;
    	else l = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}