BZOJ4585 「APIO2016」烟火表演

题解
可并堆

Description

给定一棵以 $1$ 为根的 $n$ 个节点的树，每条边有一个边权。有 $m$ 个叶子。将一条边的边权从 $x$ 修改至 $y$ 需要的代价是 $|x-y|$ 。求将所有叶子到根节点的距离修改成相同的最小代价。

Solution

神仙题。参考：https://blog.csdn.net/u014609452/article/details/52347062；洛谷题解第一篇。

定义 $f_x(y)$ 表示将以 $x$ 为根的子树中所有叶子结点到 $x$ 节点的距离都修改成 $y$ 所需要的代价。我们得到的结论是：$f_x$ 是个分段函数，每一段为一个一次函数，并且下凸（即一个凸壳）。

这个结论的证明要用到数学归纳法，不多赘述。

考虑维护这个凸壳。即现在已知每个儿子的凸壳，应该如何合并出这个节点的凸壳。

儿子节点的凸壳首先需要往其中加入父亲到他的这一条边。可以证明有了这一条边后依然是一个凸壳。

对每个儿子都这么做，得到的所有凸壳相加即为父亲节点的凸壳。

于是问题变为如何维护 ”往上增加一条边“ 后凸壳的变化。

设增加这条边的边权是 $w$ ，要增加的这个函数是 $f$ ，新的函数是 $g$ ，最小值在 $L$ 到 $R$ 取到。

  1. 对于 $x \leq L$ ，此时要把新加的这条边减成 $0$ ，代价 $w$ 即 $g(x) = f(x) + w$
  2. 对于 $L \leq x \leq L + w$ ，此时先将原来的子树里的每个叶子到根的距离修改成 $L$ ，加上 $w$ 后要再修改成 $x$ 需要 $L + w - x$ 的代价 （先把 $w$ 的边干掉然后用 $L - x$ 的代价从 $L$ 到 $x$ ）。即 $g(x) = f(x) + w + L -x$
  3. 对于 $L + w \leq x \leq R + w$ ，此时 $g(x) = f(x - w)$ 。又因为 $x - w \in [L, R]$ 都是最小值，所以 $g(x) = f(L)$
  4. 对于 $R+w \leq x$ ，此时先将原来的子树里的每个叶子到根的距离修改成 $R$ ，加上 $w$ 再修改成 $x$ 需要 $|R + w - x| = x - w - R$ （其实和 2 差不多只是正负的问题）。即 $g(x) = f(x) + x - w - R$

容易看出，$g$ 的最小值在 $[L + w, R + w]$ 取到。

得到这些性质后，我已经自闭了… 我们可以分析它的几何意义。

第一段（$x \leq L$） 相当于是往上做了一个平移。

第二段（$L \leq x \leq L + w$）你会发现，$g(x) = f(x) + w - L - x$ 中有一个 $-x$ 。这说明这一段的斜率是 $-1$

第三段（$L + w \leq x \leq R + w$）这一段其实就是一段平的（这也是为啥它是新函数取到最小值的段），斜率维 $0$

第四段（$R + w \leq x$ ）你会发现，$g(x) = f(x) + x - w - R$ 有一个 $+x$ 。这说明这一段的斜率是 $1$

这样我们就知道了新凸壳与原来的凸壳的区别：将 $L$ 左边一段向上平移，删除右边，新增两个拐点 $L+w, R+w$ 并且 $L$ 到 $L+w$ 的斜率为 $-1$ ，$L+w$ 到 $R + w$ 的斜率是 $0$，$R + w$ 往右的斜率是 $1$ 。

有了这个结论，然后的做法其实还不是很显然（至少对我来说）。

这个凸壳还有一个可以证明的性质：（从左到右）每当经过一个拐点，那么斜率会增加 $1$

我们可以对每个点存放凸壳的拐点（的横坐标）。

每次将儿子节点的凸壳弹出后面的（从大到小）拐点，然后加入两个新拐点。然后将儿子节点的拐点合并到该节点的凸壳中。

这个过程中，需要支持：删除（横坐标）最大的拐点；合并。自然想到可并堆。

还剩下几个小问题：

  1. 实现时，如何弹出拐点直到最小值的那一段？最右边的那一段的斜率是儿子数量。（因为每合并一次右端斜率 ++） 所以弹出儿子数量个拐点即可。
  2. 最后的答案如何计算？或：最小值那一段该如何计算？ $f_1(0)$ 很好计算，为所有边权的和。我们又知道，每一个拐点使得斜率++。于是可以先把右边的点弹掉（儿子个），然后计算即可

还有一个很骚的操作，即一种快乐的可并堆：

1
2
3
4
5
6
7
int merge(int x, int y) {
  if(!x || !y) return x + y; 
  if(vx[x] < vx[y]) swap(x, y); 
  int d = rand() % 2; 
  ch[x][d] = merge(ch[x][d], y); 
  return x; 
}

懒人专用，复杂度很对（426ms）。会证明复杂度的可以私信我，我太菜了不会证…

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
70
71
72
73
/**
 * Author: AcFunction
 * Date:   2019-03-19 21:45:47
 * Email:  3486942970@qq.com
**/

#include <bits/stdc++.h>
#define ll long long
#define db double
#define PII pair <int, int> 
#define pb push_back 
#define Fi first
#define Se second 
#define MP make_pair
#define RG register 
#define rep(i, l, r) for(RG int i = l; i <= r; i++) 
#define per(i, r, l) for(RG int i = r; i >= l; i--)

using namespace std;

void INIT() {
  ios :: sync_with_stdio(false); cin.tie(0); 
}

template < typename T > void sc(T& t) {
  char c = getchar(); T x = 1; t = 0; while(!isdigit(c)) {if(c == '-') x = -1; c = getchar();}
  while(isdigit(c)) t = t * 10 + c - '0' , c = getchar();t *= x;
}
template < typename T , typename... Args > void sc(T& t , Args&... args) {sc(t); sc(args...);}


const int N = 600300; 

int n, m, fa[N], son[N];
ll w[N], ans, vx[N];  

int cnt, ch[N][2], rt[N];  

int New(ll x) {
  vx[++cnt] = x; ch[cnt][0] = ch[cnt][1] = 0; return cnt; 
}

int merge(int x, int y) {
  if(!x || !y) return x + y; 
  if(vx[x] < vx[y]) swap(x, y); 
  int d = rand() % 2; 
  ch[x][d] = merge(ch[x][d], y); 
  return x; 
}

int main() {
  // INIT(); 
  srand((unsigned long long)new char); 
  sc(n, m); 
  for(int i = 2; i <= n + m; i++) {
    sc(fa[i], w[i]); ans += w[i]; son[fa[i]]++; 
  }
  for(int i = n + m; i >= 2; i--) {
    for(int j = 1; j <= son[i] - 1; j++)
      rt[i] = merge(ch[rt[i]][0], ch[rt[i]][1]); 
    ll R = vx[rt[i]]; rt[i] = merge(ch[rt[i]][0], ch[rt[i]][1]); 
    ll L = vx[rt[i]]; rt[i] = merge(ch[rt[i]][0], ch[rt[i]][1]); 
    rt[i] = merge(rt[i], merge(New(L + w[i]), New(R + w[i])));  
    rt[fa[i]] = merge(rt[fa[i]], rt[i]); 
  }
  for(int j = 1; j <= son[1]; j++) 
    rt[1] = merge(ch[rt[1]][0], ch[rt[1]][1]); 
  while(rt[1]) {
    ans -= vx[rt[1]]; 
    rt[1] = merge(ch[rt[1]][0], ch[rt[1]][1]); 
  } printf("%lld\n", ans); 
  return 0; 
}