P3994 高速公路

Description

C国拥有一张四通八达的高速公路网树,其中有n个城市,城市之间由一共n-1条高速公路连接。除了首都1号城市,每个城市都有一家本地的客运公司,可以发车前往全国各地,有若干条高速公路连向其他城市,这是一个树型结构,1号城市(首都)为根。假设有一个人要从i号城市坐车出发前往j号城市,那么他要花费Pi*(i城市到j城市的距离)+Qi元。由于距离首都越远,国家的监管就越松,所以距离首都越远,客运公司的Pi(单位距离价格)越大,形式化的说,如果把高速路网看成一棵以首都为根的有根树,i号城市是j号城市的某个祖先,那么一定存在Pi<=Pj。

Solution

如果把树上的链单独拿出来考虑的话, 可以列出dp方程
$$
f_i = \min f_j+dis_j\cdot P_i +q_i
$$
可以考虑使用斜率优化, 当从$j$转移比$k$更优时满足
$$
f_j+dis_{i,j}\cdot P_i +q_i< f_k+dis_{i,k}\cdot P_i +q_i$$
$$\Rightarrow P_i >\frac{f_j-f_k}{dis_{i,k}-dis_{i,j}}
$$
考虑到这里我就没有办法了, 因为这需要维护一个单调队列, 而后效性使得每个拥有多个子节点的结点必须单独保存一个单调队列, 这需要大量的空间.
无奈之下, 求助于XXY学姐的Blog.

只需要考虑如何去除兄弟节点的子树对单调队列的影响
即在一个节点退出dfs时,将单调队列恢复为这个节点开始dfs的情况
头指针只是不断的+1,没有涉及到单调队列中元素的修改,所以记录下头指针在哪个位置即可
尾指针涉及到元素的替换,但是它只会替换一个元素,所以记录下尾指针的位置,以及被当前点替换的元素是谁
当节点退出dfs时,恢复记录的这三个值即可
这样的话,一个节点多次出队入队,时间复杂度就不是O(n)了
所以二分出队位置,时间复杂度为O(nlogn)

发现这个后效性好像也没有那么的难处理, 只要仔细观察和分析就能发现它的性质.

Code

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
// 维护一个单调递增的队列来斜率优化
// 每次去掉队列头小于P_i的元素
// 每次更改队列时只是更改了其中一个元素, 移动了队列尾和队列头而已.
#include <stdio.h>
#include <iostream>
#include <algorithm>
const int N = 1000006;
using std:: pair;
using std:: make_pair;
struct Edge {
int v, nxt;
}e[N << 1];
int head[N], tot;
int p[N], Q[N], d[N];
long long dis[N], f[N];
void AddEdge(int u, int v) {
e[++tot] = (Edge) {v, head[u]}; head[u] = tot;
}
namespace {
int h = 0, t = -1, q[N];
double slope(int y, int x) {
return (double)(f[y] - f[x]) / (double)(dis[y] - dis[x]);
}
void print() {
puts("Begin:");
for (int i = h; i <= t; i += 1)
printf("%d ", q[i]);
puts("\n:End");
}
}
/*
3
1 1 1 6
2 9 2 4
*/
pair<int, int> dfs(int u, int fa) {
dis[u] = dis[fa] + d[u]; // 得到点到树根距离
while (h < t and slope(q[h + 1], q[h]) <= p[u]) h += 1; // 因为p和dis单调性
f[u] = f[q[h]] + (dis[u] - dis[q[h]]) * p[u] + Q[u]; // 计算当前点的答案
while (h < t and slope(u, q[t]) < slope(q[t], q[t - 1])) t -= 1; // 加当前点加入队列
int Re = t + 1, OO = q[t + 1]; q[++t] = u; // 记录被替换的位置
/*************************************************************/
// printf("Status: %d %d\n", u, f[u]);
// print();
/*************************************************************/
int bH = h, bT = t; // 记录队列的头和尾
for (int i = head[u]; i; i = e[i].nxt) { // 枚举当前点的出边
pair<int, int> g = dfs(e[i].v, u); // 被替换的位置和值
h = bH, t = bT, q[g.first] = g.second; // 恢复递归前的队列
}
return make_pair(Re, OO);
}
int main () {
int n; scanf("%d", &n);
for (int i = 2, tmp; i <= n; i += 1) {
scanf("%d%d%d%d", &tmp, &d[i], &p[i], &Q[i]);
AddEdge(tmp, i);
}
dfs(1, 0);
for (int i = 2; i <= n; i += 1)
printf("%lld\n", f[i]);
return 0;
}
-------------本文结束感谢您的阅读-------------