题解 P3642 【[APIO2016]烟火表演】
超神！！！根本想不到啊！
我可是理解了好久好久的喵呜。。。(σ-`д･´)
题解比代码还长.jpg
/*
* 令f(x)表示将某个点为根的子树中所有叶子到它的距离置为x的最小代价；
* 发现它是一个下凸函数，并且是线性的，即一次函数；
* 形象地理解一下，最小值左边的部分，大部分是由原来的长度减去值得到；
* 最小值右边的部分，大部分是由原来的长度加上值得到；
* 考虑一个点u，从所有儿子v转移过来；
* 过程分两步：
* <1> 将所有v的凸包加上u-v这条边；
* <2> 将加完边的凸包合并；
* 假设现在要加一条边w，f(x)在x属于[L,R]是取到最小值，要从f(x)转移到f'(x)；
* 分四种情况：
* +================================================================+
* 1.x<=L f'(x)=f(x)+w;
* 原来这部分都是减去值得到，现在加了一条边之后仍要得到这个值x；
* 所以也必须要减去值才能满足，故直接减去w，将这条边变为0；
* 2.L<=x<=L+w f'(x)=f(L)+w-(x-L)
* 这一段是从x=L开始的斜率为-1的一次函数；
* 由于之前将这条边减为0了，现在一点点加回去，相应的代价就逐渐减少1；
* 3.L+w<=x<=R+w f'(x)=f(L)
* 将原先的取到最小值的部分转移到了这一段；
* 4.R+w<=x f'(x)=f(L)+(x-R)-w
* 这一段是从x=R+w开始的斜率为1的一次函数；
* 原因是到了这里以后，每次只要在w这条边上+1即可；
* +================================================================+
* 总结一下即，将[L,R]一段向右平移，[0,L]一段向上平移；
* 中间插入一段斜率为-1的线段，再将右边改为斜率为1的直线；
* 合并操作只要将函数相加即可；
* 考虑怎么维护：
* 不失一般性，认为每一个拐点都能使斜率+1；
* ///观察///：
* - 每次加边后，会让凸包最右端斜率为1，即一次合并后最右端斜率即为儿子个数；
* - 凸包左边一段借据已知，即f(0)=边权和；
* 据此推算凸包表达式：
* 设此时拐点个数为p，根的儿子个数为d，总边权和为s；
* 则f(x)在0处的表达式为：f(x)=-(d-p)*x+s；
* 从小到大扫描每个拐点就能得到整个凸包的表达式；
* 我们现在只关心拐点的横坐标位置；
* 考虑用可合并大根堆存储拐点；
* 于是 <1> 就变成了：从堆中弹出点直到斜率为0，再将[L,R]右移以后的两个拐点加入；
* <2> 就直接合并即可；
* 最后计算答案只需找到斜率为0的那一段计算代价即可；
* 神题啊！
*/
#include<bits/stdc++.h>
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)
#define N 600010
#define ll long long
using namespace std;
int n, m, tot, fa[N], w[N], d[N], rt[N];
ll sum;
struct heap {//左偏树，维护大根堆
int l, r, dis; ll v;//v存当前点的横坐标值
} tr[N];
inline int merge(int x, int y) {
if(!x || !y) return x+y;
if(tr[x].v < tr[y].v) swap(x, y);
tr[x].r = merge(tr[x].r, y);
if(tr[tr[x].l].dis < tr[tr[x].r].dis) swap(tr[x].l, tr[x].r);
if(!tr[x].r) tr[x].dis = 0; else tr[x].dis = tr[tr[x].r].dis+1;
return x;
}
inline int pop(int x) { return merge(tr[x].l, tr[x].r); }
int main() {
scanf("%d%d", &n, &m);
rep(i, 2, n+m) {
scanf("%d%d", &fa[i], &w[i]);
sum += w[i]; d[fa[i]] ++;//d[]儿子个数，sum边权和
}
per(i, n+m, 2) {
ll l = 0, r = 0;//l,r保存当前的斜率为0的一段
if(i <= n) {
while(--d[i]) rt[i] = pop(rt[i]);//不停弹出最大的点，直到斜率为0；点数刚好是儿子数
r = tr[rt[i]].v; rt[i] = pop(rt[i]);
l = tr[rt[i]].v; rt[i] = pop(rt[i]);
}
tr[++tot].v = l+w[i]; tr[++tot].v = r+w[i];
rt[i] = merge(rt[i], merge(tot, tot-1));
rt[fa[i]] = merge(rt[fa[i]], rt[i]);//合并儿子
}
while(d[1]--) rt[1] = pop(rt[1]);
while(rt[1]) { sum -= tr[rt[1]].v; rt[1] = pop(rt[1]); }
printf("%lld\n", sum);
return 0;
}