[NOIP2015]运输计划|树上前缀和+树上差分

主要在普通差分的基础上介绍一下树上差分。

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

输入输出格式

输入格式:

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

接下来 n−1 行描述航道的建设情况,其中第 i 行包含三个整数 ai,bi 和 ti,表示第 i 条双向航道修建在 ai与 bi 两个星球之间,任意飞船驶过它所花费的时间为 ti。数据保证 1≤ai,bi≤n且 0≤ti≤1000。

接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj 和 vj,表示第 j 个运输计划是从 uj号星球飞往 vj号星球。数据保证 1≤ui,vi≤n

输出格式:

一个整数,表示小 P 的物流公司完成阶段性工作所需要的最短时间。

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
6 3 
1 2 3
1 6 4
3 1 7
4 3 6
3 5 5
3 6
2 5
4 5

输出样例#1:

1
11

说明

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

img

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


去年看这道题的时候,一脸懵逼

现在也是觉得这题其实也不难。

简化一下题意就是,有一个节点数为n的有权树,现在给你m条路径的两个端点,让你删除任意一条边,使删除边后的m条路径中最大的那条路径最小。

因为是棵树,显然任意两点的距离就是这个点到他们lca的距离加上那个点到lca的距离。这个距离显然是唯一的。那么我们可以在起始建树的时候记录到当前节点的前缀距离和,假如是c[i],那么显然路径的长度就是c[左端点]-c[LCA]+c[右端点]-c[LCA]。

考虑最大值最小,可以用二分答案用log的时间复杂度,将问题转化为判定性问题。显然二分的就是当前的最大路径长度。

现在问题变成了,在树上有一些已知的路径,判断删除某条边后是否全部的路径长度都小于等于x。考虑在删边之前如果一条路径的长度大于了x,那么显然应该删除的边就在这条路径上。先将这些路径标记起来,如果能找出一条这些路径都覆盖的边(因为只能改一条边,有多条路径大于x,那么肯定x在这些边之中),且该边的权值>=最长路径-x,那么这个方案是可行的。 那么这些边怎么找呢?

树上差分(不会普通差分的同学建议学习后再看本文)。

虽然也可以用树链剖分做,但是树链剖分并不在NOIP范围之内,而且就码量和理解难易程度上而言,树上差分显然要更适合NOIP。

首先,我们要知道,一棵树如果有n个叶子结点,那么这棵树可以看做是n条有重叠部分的链组成。这句话很重要,一定揣摩清楚。

树上差分分为对边的差分和对点的差分,但其实基本原理是一样的。本题中是对边的差分,基本思想就是,用d[i]表示从i到i的父亲节点这一条路径所经过的次数。把d[i]加上1,表示从根节点到i的路径中的所有边都又被访问了一遍。如果我们要访问某条边经过的次数,我们就可以从根节点x向上访问,访问到它的父亲节点v,然后将d数组求前缀和,然后继续向上重复这个操作,这样前缀和就是该边访问过的次数。

但是本题中我们要做的是将两个节点到他们LCA的路径进行标记而不是到根节点。那么我们考虑对两个节点都做上述操作,首先两节点间的路径肯定都是1(我们假设还没有进行过任何操作)。那么LCA之上的部分显然两次标记是重合的,也就是说LCA之上的边我们标记了两次。还记得普通差分的思想吗?如果我们的加影响到了后面不改加的怎么办?对,在第一个不该被影响的地方再减去该值。树上差分也是如此,不过不同的是,这里要写成d[LCA]-=2;而且因为树的结构问题,我们由普通差分的求前缀和转化为了求树的后缀和,也就是从叶子结点向根节点。因为每个节点只有一个父亲节点,所以每次修改其实相当于修改了一条链,这条链上的操作与普通差分无异。如果觉得不理解,可以在纸上手动演算一下。

因此这道题我们的差分算法是:将两个节点处d数组++,将其LCAd数组-=2。然后对树求一遍后缀和。注意求后缀和时要求从树的深度最低的一层向高一层递推,所以需要dfs序的辅助,因为dfs序从n到1,一定是对于每条链(前面提到每次修改实际上是修改了一条链)都是从深度低向深度高扩展。

现在我们得到了每条边的经过次数,就可以求解了。

这样求解完毕之后,我们会发现还是会T掉一个点。听说用tarjan求LCA会更好,但我没试过。观察题目我们发现,数据范围的最后给出了一句话:请注意常数因子带来的程序效率上的影响。那么我们还有哪里可以优化常数呢?

找来找去,只有二分答案的左右端点值。

如果左端点设为0就会T掉一个点。如果你足够聪明,你就会发现左端点在某些情况下远远到不了0。这种极限情况是:右端点很大,答案十分靠近右端点,而右端点与0的距离很大。这种情况下算法复杂度就会被卡到$O(nlogn)​$,n是3e5,所以时间比较吃紧。考虑我们每次找到每条路径上最长的那条边,显然左端点就是up减去这条边的长度。

可以通过本题。时间复杂度$O(能过)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <map>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 300010;
const int MAXM = 300010;
int n, m, u[MAXM], v[MAXM];
int maxx = 0, up = 0;
int fat[MAXN][25], dep[MAXN];
int lca[MAXN], c[MAXN], dis[MAXM];
int dfn[MAXN], d[MAXN], num, val[MAXN];

struct Edge {
int to, nxt, w;
}e[MAXN << 1];

template <typename _Tp>
inline void read(_Tp &x) {
char ch = getchar( ); bool f = 0; x = 0;
while (!isdigit(ch)) { if (ch == '-') f = 1; ch = getchar( ); }
while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar( ); }
x = f ? -x : x;
}

int head[MAXN], tot;
void AddEdge(int x, int y, int z) {
e[++ tot].to = y, e[tot].w = z;
e[tot].nxt = head[x], head[x] = tot;
}

void Build(int s, int fa) {
dfn[++ num] = s;;
for (int i = head[s], v; i; i = e[i].nxt) {
v = e[i].to;
if (v == fa) continue;
dep[v] = dep[s] + 1;
fat[v][0] = s;
c[v] = c[s] + e[i].w;
val[v] = e[i].w;
Build(v, s);
}
}

int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = 23; i >= 0; -- i)
if (dep[fat[x][i]] >= dep[y])
x = fat[x][i];
if (x == y) return x;
for (int i = 23; i >= 0; -- i)
if (fat[x][i] != fat[y][i]) {
x = fat[x][i];
y = fat[y][i];
}
return fat[x][0];
}

bool cheak(int x) {
memset(d, 0, sizeof(d));
num = 0;
for (int i = 1; i <= m; ++ i)
if (dis[i] > x) {
d[u[i]] ++; d[v[i]] ++;
d[lca[i]] -= 2;
num ++;
}
for (int i = n; i; -- i) {
d[fat[dfn[i]][0]] += d[dfn[i]];
if (val[dfn[i]] >= up - x && d[dfn[i]] == num) return true;
}
return false;
}

int main( ) {
read(n), read(m);
int a, b, t;
for (int i = 1; i < n; ++ i) {
read(a), read(b), read(t);
AddEdge(a, b, t);
AddEdge(b, a, t);
maxx = max(maxx, t);
}
dep[0] = -1;
dep[1] = 1;
Build(1, 0);
for (int j = 1; j <= 23; ++ j)
for (int i = 1; i <= n; ++ i)
fat[i][j] = fat[fat[i][j - 1]][j - 1];
for (int i = 1; i <= m; ++ i) {
read(u[i]), read(v[i]);
lca[i] = LCA(u[i], v[i]);
dis[i] = c[u[i]] + c[v[i]] - c[lca[i]] * 2;
up = max(up, dis[i]);
}
int l = up - maxx, r = up + 1, mid, ans;
while (l <= r) {
mid = (l + r) >> 1;
if (cheak(mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
printf("%d\n", ans);
return 0;
}
{% if theme.fireworks %} {% endif %} {{ live2d() }}