题解 P3642 【[APIO2016]烟火表演】

可并堆好题啊…… 不是很明白为啥左偏树是最常见的可并堆…… ~~明明配对堆比左偏树又快又好写~~ 除了可持久化可并堆这种东西以外左偏树似乎没有什么存在价值啊 ~~但是这题又不需要可持久化~~ _________________ # 本题题解 给定一颗树每个边上有权值,你可以任意调整每个边的权值为一个非负的整数,将一条原来权值为val的边的权值调整为a的代价是$|val-a|$,要求调整完边权之后每个叶子到根的距离是相等的,求最小代价 ### 从一个naive的dp开始 那么我们可以设计一个非常naive的dp状态就是$dp(u,i)$表示将u子树中的所有叶子节点调整至距u的父亲距离为$j$的最小代价 那么我们的转移方程也是十分的平凡的,枚举u和父亲的边到底变成了什么值然后进行取min操作 可以推出这样的一个式子 $$f(u,i)=\min_{k=0}^{i}|val-k|+\sum_{v \in u.son}f(v,i-k)$$ _____________ ### 观察式子的特点 我们发现我们处理的函数是一个类似于min卷积一样的式子, 显然快速的计算这个东西是没什么可能的…… 不过我们的$f(u,x)$这个函数相当的有特点，在接下来我们将会使用归纳法证明$f(u,x)$是一个关于x的分段函数并且在每段都是线性的 那么对于函数的min卷积这个运算，尽管一般情况下是没有什么性质的，但是在这道题里我们有一个函数是绝对值函数，而另一个函数是一个简单的分段函数 此时我们就有可能会有一些性质了 那么我们手动分情况大力讨论一波……（想证明的人自己手丸去吧,推式子推了我一个下午） 会发现min卷积大概有这么几个性质 1.一个斜率比-1大的直线卷积上斜率为-1的直线之后新函数截距为两个函数的截距之和,斜率不变 2.一个常数函数和一个斜率为-1的直线卷积之后截距为两个函数截距之和而斜率变为-1 3.对于一个下凸的分段函数并且每一段的斜率都大于1,和一个斜率为+1的直线卷积之后,这个函数将会变成一条斜率为1的直线 事实上刚才的结论只是一个感性理解,因为我们在卷积的时候远不止这几种情况 然后我们胡乱爆推一波结论之后可以得到这个式子,如果我们给$f(u,x)$这个函数添加一条父亲边的话我们函数会做这样的变化，假设这个函数在$[L,R]$处取值为0 1.将函数在$[1,L]$的一段向上平移$val$个单位 2.将函数在$[R,+\infty]$的一段向右平移$val$个单位并且斜率改为+1 3.将函数在$[L,R]$的一段向右平移$val$个单位 4.此时你发现中间空出了一段斜率为-1,$val$个单位高$val$个单位宽的线段,在中间插入一个线段就行了 合并相邻的子树就是将函数简单的相加起来 那么我们采用这样的方式来存储一个函数$f(u,x)$ 通过数学归纳法可以得到$f(u,x)$的最右端斜率等于1,而在插入父亲之前函数的最左段斜率=u的儿子数目 我们现在通过存储这个分段函数的每一个拐点的x坐标来表示这个函数 并且我们认为，**从右向左,每经过一个拐点，函数的斜率-1** 那么初始的时候我们需要存储一个绝对值函数,这样的话我们就用两个在同一个位置的拐点来描述这个绝对值函数 这样储存函数有一个好处就是当我们把函数相加的时候只需要简易的将两个函数的拐点列表合并一下再将最右端斜率简单相加就可以完成函数的合并工作了 那么我们现在已经可以完成函数相加的操作了,我们现在需要兹瓷的操作就是将函数所有斜率为正的拐点全部弹出这个操作了(至于修改斜率什么的其实简单的就是插入两个拐点就行了) 那么我们发现其实这个操作就等价于弹出函数中x坐标前k大的拐点其中k为我们当前处理的点的孩子个数 那么这个操作很显然就是删除k次最大值 又发现我们之前将两个函数相加的操作就是将两个函数的拐点列表合并 所以我们写一个可并的大根堆(或者直接使用pb_ds)就可以完成合并函数和插入一条边的操作了 最后我们得到了根节点的函数,显然$f(root,0)=\sum val$也就是所有边的和,而最右段的斜率就是根节点的度数，我们还知道每经过一个点函数的斜率就会-1,因此根据这3点我们就可以反推出整个函数的表达式 然后就可以做了,提取一下这个分段函数斜率为0的那一段值就ok了 这里使用了配对堆来实现可并堆 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> using namespace std;const int N=6*1e5+10;typedef long long ll; template <class T> void read(T &x){ char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } int n;int m;ll tot;ll ans[N];int tp; namespace par_hp//简易配对堆板子 { int x[N];int al[N];int ct;ll val[N]; inline void add(int u,int v){x[v]=al[u];al[u]=v;} inline int mg(int u,int v) { if(!u)return v;if(!v)return u; if(val[u]<val[v])swap(u,v);add(u,v);return u; } inline int fpop(int u) { if(!u)return 0;if(!x[u])return u;int v1=x[u];int v2=x[v1]; x[u]=x[v1]=0;return mg(mg(u,v1),fpop(v2)); } inline void dfs(int u){ans[++tp]=val[u];for(int i=al[u];i;i=x[i])dfs(i);} struct hp//为了方便起见单独封了一个可并堆结构体 { int rt; inline void push(const ll& x){val[++ct]=x;rt=mg(rt,ct);} inline ll top(){return val[rt];} inline void pop(){rt=fpop(al[rt]);} inline void join(int p){rt=mg(rt,p);} }; }par_hp::hp h[N];int fa[N];ll val[N];int d[N];ll sum; int main() { read(n);read(m); for(int i=2;i<=n+m;i++)read(fa[i]),read(val[i]),d[fa[i]]++,sum+=val[i]; for(int i=n+m;i>1;i--) { ll l=0;ll r=0;//合并 while(d[i]--){r=h[i].top(),h[i].pop();}l=h[i].top();h[i].pop(); h[i].push(l+val[i]);h[i].push(r+val[i]);h[fa[i]].join(h[i].rt); }par_hp::dfs(h[1].rt);sort(ans+1,ans+tp+1);tp-=d[1];//处理函数 for(int i=1;i<=tp;i++) sum-=(ll)(ans[i]-ans[i-1])*(tp-i+1);printf("%lld\n",sum); } ```