APIO2016烟火表演 可并堆

发表于 更新于 分类于 阅读次数：

[APIO2016]烟火表演 大约是退役前最后一篇题解，把之前的坑填上。只说一下思路，细节可以看其它题解 首先考虑一个DP：令$f_{x,i}$表示$x$点，到叶子的长度为$i$的最小代价。那么考虑合并，有$f_{x,i} = \min_{j \leq i} f_{y,j} + i-(j+c)$。 考虑把这个DP分步进行：首先把到父亲的边加上，之后合并。令加上到父亲边后的函数为$g$ 可以注意到，$f$是一个凸函数。并且这个函数的斜率是整数。可以感性理解这个结论：当长度变化时到一定阶段时，需要调整更多的边。并且每条边的代价都是$1$。 那么考虑对$g$的求解：小于$\min f$时，只调整父亲边，大于时使用$\min f$并调整父亲边。中间部分是平的。核心思想就是使用靠近$\min f$的值 注意到分界点数量是$O(n)$的，可以维护分界点。每次合并分为以下过程：找到平的一段，把它后面的删掉，在平的前后各插入一条线。 于是用可并堆维护分界点即可。有几个地方：

  1. 如何维护分界点：假设每个点都让斜率+1即可
  2. 如何找到平的一段：根据做法归纳可知只需弹掉度数-1个
  3. 如何修改分界点：注意到需要做的操作是加入斜率为-1的一段，可以平移它后面的一段（即min）实现
  4. 如何求答案：答案即到父亲边权为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
#include <bits/stdc++.h>

const int N = 2e6 + 233;

int n, m, p[N], c[N], deg[N];
int ls[N], rs[N], root[N];
long long val[N];
int now;
long long ans;

int merge(int x, int y) {
  if (!x  !y) return x + y;
  if (val[x] < val[y]) std::swap(x, y);
  rs[x] = merge(rs[x], y);
  if (rand() & 1) std::swap(ls[x], rs[x]);
  return x;
}

inline int pop(int x) {
  return merge(ls[x], rs[x]);
}

int main() {
  srand(114514);
  scanf("%d%d", &n, &m);
  for (int i = 2; i <= n + m; ++i)
    scanf("%d%d", p + i, c + i), ++deg[p[i]];
  now = n + m;
  for (int x = n + m; x > 1; --x) {
    long long l = 0, r = 0;
    if (x <= n) {
      for (int i = 1; i < deg[x]; ++i)
        root[x] = pop(root[x]);
      r = val[root[x]], root[x] = pop(root[x]);
      l = val[root[x]], root[x] = pop(root[x]);
    }
    val[++now] = l + c[x];
    val[++now] = r + c[x];
    root[p[x]] = merge(root[p[x]], merge(root[x], merge(now - 1, now)));
  }
  for (int i = 1; i <= deg[1]; ++i)
    root[1] = pop(root[1]);
  for (int i = 2; i <= n + m; ++i)
    ans += c[i];
  while (root[1])
    ans -= val[root[1]], root[1] = pop(root[1]);
  printf("%lld\n", ans);
  return 0;
}