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;
}