Chro's Blog


同じ世界に、立っていたんだ。


「BZOJ 4585」「UOJ 205」「APIO2016」Fireworks

  1. 1. 输入格式
  2. 2. 输出格式
  3. 3. 样例
    1. 3.1. input
    2. 3.2. output
  4. 4. 限制与约定
  5. 5. 题解

烟花表演是最引人注目的节日活动之一。在表演中,所有的烟花必须同时爆炸。为了确保安全,烟花被安置在远离开关的位置上,通过一些导火索与开关相连。导火索的连接方式形成一棵树,烟花是树叶,如图所示。火花从开关出发,沿导火索移动。每当火花抵达一个分叉点时,它会扩散到与之相连的所有导火索,继续燃烧。导火索燃烧的速度是一个固定常数。图中展示了六枚烟花 {E1,E2,…,E6} 的连线布局,以及每根导火索的长度。图中还标注了当在时刻 0 从开关点燃火花时,每一发烟花的爆炸时间。

Hyunmin 为烟花表演设计了导火索的连线布局。不幸的是,在他设计的布局中,烟花不一定同时爆炸。我们希望修改一些导火索的长度,让所有烟花在同一时刻爆炸。例如,为了让图中的所有烟花在时刻 13 爆炸,我们可以像下图中左边那样调整导火索长度。类似地,为了让图中的所有烟花在时刻 14 爆炸,我们可以像下图中右边那样调整长度。

修改导火索长度的代价等于修改前后长度之差的绝对值。例如,将上面那副图中布局修改为下面那副图的左边布局的总代价为 6,而修改为右边布局的总代价为 5。

导火索的长度可以被减为 0,同时保持连通性不变。

给定一个导火索的连线布局,你需要编写一个程序,去调整导火索长度,让所有的烟花在同一时刻爆炸,并使得代价最小。

输入格式

所有的输入均为正整数。令 N 代表分叉点的数量,M 代表烟花的数量。分叉点从 1 到 N 编号,编号为 1 的分叉点是开关。烟花从 N+1 到 N+M 编号。

输入第一行为 N,M。后面 N+M−1 行,第 i 行两个整数 Pi+1,Ci+1。其中 Pi 满足 1≤Pi<i,代表和分叉点或烟花 i 相连的分叉点。Ci 代表连接它们的导火索长度(1≤Ci≤109)除开关外,每个分叉点和多于 1 条导火索相连,而每发烟花恰好与 1 条导火索相连。

输出格式

输出调整导火索长度,让所有烟花同时爆炸,所需要的最小代价。

样例

input

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

output

1
5

限制与约定

子任务 1(7 分):N=1,1≤M≤100。

子任务 2(19 分):1≤M≤300,且开关到任一烟花的距离不超过 300。

子任务 3(29 分):1≤M≤5000。

子任务 4(45 分):1≤M≤300000。

题解

子任务 1 是一个提示。在该子任务中,输入是一个菊花图。这种情况下的最优策略是把每条边都改成中位数。

那么推广到任意情形,代价和目标长度之间形成一个函数关系 f(x)。这个函数是一个下凸函数。更具体地说,函数的图象是一个分段的、下凸的「下凸壳」。

按照树型 DP 的一般规律,我们自叶子起向上 DP,也就是说要从叶子节点开始逐步向上合并这些凸壳。

合并时有两种操作:

  1. 从当前节点伸展出一条向父节点的边,修改凸壳;
  2. 上层节点接收这些凸壳,合并成一个新的凸壳。

首先考虑如何暴力维护凸壳。

对于操作 1,设当前凸壳函数为 H(x),边的长度为 w,那么:

$$H'(x)=\begin{cases} H(x)+w & (x \le L) \\ H(L)+w-(x-L) & (L \le x \le L+w) \\ H(L) & (L+w \le x \le R+w) \\ H(L)+(x-R)-w & (x \ge R+w) \end{cases}$$

对于操作 2,总有 $H'(x)=H_1(x)+H_2(x)$,直接暴力相加就好。


然后考虑优化计算方案。一个容易想到的做法是启发式合并或者平衡树……然而一副很难写+卡常的样子(这样做的时间复杂度是 $O((n+m)\log_2^2(n+m))$,在 30W 的数据规模下显得十分捉急)。

这个凸壳满足所有斜率都是整数。因为从上面的合并公式中,我们可以看到,x 前的额外系数只有 -1 和 1。

而同时我们也看到,操作 1 对图象的变化就等价于「左边平移,中间插入三段,这三段的斜率分别是 -1/0/1」。

因此,我们可以试图只保存凸壳拐点的横坐标——这是可以做到的,我们可以在必要的情况下把一些拐点拆点,这样能使每个拐点总是使斜率 +1。

而每次操作 1,就等价于插入两个新的拐点,根据上文公式,这两个拐点是 L+w 和 R+w。

同时我们又得到了一个结论:在上述做法的前提下,凸壳最右端的斜率,就是当前节点的儿子个数。


我们用可并堆来维护拐点序列。这个可并堆是一个大根堆,堆元素是每个拐点的横坐标。

每次操作 1 时,把所有斜率 >=0 的拐点全部删掉(因为没用),然后添加两个新的拐点。

而操作 2 就是可并堆的合并操作。

最后处理到根节点时,删掉 (out_degree(1) - 1) 个拐点,把剩下的拐点全部取出来,然后由于每个拐点都是使斜率 +1,那么我们只要知道 x=0 时的函数值(也即 H(0)),然后依次减掉每个最后剩下的拐点的横坐标即可。而这个 H(0) 根据题意,就是初始时所有边权之和。

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
#include <bits/stdc++.h>
using namespace std;
#define long long long
const int maxn = 300005;
const long inf = 1ll << 60;
struct heap {
heap *lc, *rc;
long val, dis;
} *null, *id[maxn];
int n, m, par[maxn], len[maxn], deg[maxn];
int tot;
long p[maxn];
long ans;
heap *merge(heap *x, heap *y) {
if (x == null) return y;
if (y == null) return x;
if (x->val < y->val) swap(x, y);
x->rc = merge(x->rc, y);
if (x->lc->dis < x->rc->dis) swap(x->lc, x->rc);
x->dis = x->rc->dis + 1;
return x;
}
heap *newheap(long v) {
heap *o = new heap;
o->lc = o->rc = null;
o->val = v, o->dis = 0;
return o;
}
#define pop(x) x = merge(x->lc, x->rc);
int main() {
null = new heap;
null->lc = null->rc = null;
null->dis = -1, null->val = -inf;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n + m; ++i) id[i] = null;
for (int i = 2; i <= n + m; ++i) scanf("%d%d", par + i, len + i), ans += len[i], ++deg[par[i]];
for (int i = n + m; i > 1; --i) {
long L = 0, R = 0;
if (i <= n) {
while (--deg[i]) pop(id[i]);
R = id[i]->val, pop(id[i]);
L = id[i]->val, pop(id[i]);
}
id[i] = merge(id[i], merge(newheap(L + len[i]), newheap(R + len[i])));
id[par[i]] = merge(id[par[i]], id[i]);
}
while (deg[1]--) pop(id[1]);
tot = 0;
while (id[1] != null) p[++tot] = id[1]->val, pop(id[1]);
for (int i = 1; i <= tot; ++i) ans -= p[i];
printf("%lld\n", ans);
return 0;
}
最近的文章

「BZOJ 3864」「HDU 4899」Hero meet devil

DescriptionThere is an old country and the king fell in love with a devil. The devil always asks the king to do some crazy things. Although the king u…

BZOJ, DP 套 DP, HDOJ, 序列 DP 继续阅读
更早的文章

「BZOJ 2734」「HNOI2012」集合选数

Description《集合论与图论》这门课程有一道作业题,要求同学们求出{1, 2, 3, 4, 5}的所有满足以 下条件的子集:若 x 在该子集中,则 2x 和 3x 不能在该子集中。同学们不喜欢这种具有枚举性 质的题目,于是把它变成了以下问题:对于任意一个正整数 n≤100000,如何求出{1…

BZOJ, 状压 DP 继续阅读