解析

感覺是左偏樹的神題了.

首先有一個比較顯然的結論，一個合法的方案中，兩個葉子到它們 $\text{lca}$ 的距離必須相等.

考慮設計 $\text{dp}$ ：

$f_{i,x}$ 表示 $i$ 的子樹中，所有葉子到它的距離為 $x$ 的最小代價.

考慮這個函數如何向父親合并.
設一個結點到父親的距離為 $c_i$ .
樸素 $\text{dp}$ ，就有：
$$f_{i,x}=\sum _{j\in so{n}_i}\underset{v\ge 0}{\overset{x}{\min }}{f}_{j,x?v}+|c_j?v|$$
這玩意顯然復雜度爆炸啊…

換個角度，考慮 $f$ 函數本身的性質.
不難想到，原來的函數應該是一個下凸的線性函數.
$so{n}_i$ 的函數如何向 $i$ 合并？
一開始，這個函數似乎就是簡單的所有子節點函數相加合成.
并且，由于 $c_i$ 的存在，這個函數肯定要往右移 $c_i$ .
假設移動完長這樣：

但是，考慮到有 $i$ 連向 $f{a}_i$ 的邊，有些修改可以在這里一起改，就不必各自麻煩了，所以肯定函數會變化，準確的說，變得更好.

設斜率為 $0$ 的區間為 $[L,R]$ .
然后我們發現 $R$ 右側還有好多斜率大于 $1$ 的地方.
大概的實際意義就是每個兒子都各自修改.
這就很虧.
所以對于 $f_{i,x}$ 我們干脆在先全部調整成距離為 $R$，支付 $f_{i,R}$ 的代價，再把當前結點連向父親的邊權值增大 $x?R$ .
這樣就把 $R$ 右側的斜率全都變成了 $1$ .
變成這樣：

另一邊可以類似的搞嗎？
差不多，但是有個問題…
邊的權值非負！
所以我們斜率為 $1$ 的區間往左增加的長度最多為 $c_i$ .
后面的函數就往左順延 $c_i$ .
也就是變成：

別忘了，本來這個函數是整體右移 $c_i$ .
這里左邊的斜率大于1的區間又往左移動了 $c_i$ .
所以其實根本位置沒變.

總結一下的話，這個函數合并到父親后，就是 把斜率為 $0$ 的區間 $[L,R]$ 右移 $c_i$ ，把 $R$ 右邊的函數斜率全改為 $1$ ，斜率為 $0$ 的區間往右延長 $c_i$ 補上 $L$ 右移的空缺.
實現上，建一個可并堆維護所有的拐點，令相鄰拐點斜率差為 $1$ （如果兩端之間斜率差大于 $1$ 就插多個橫坐標相同的拐點），那么其實就把 $R$ 右側的所有拐點彈掉，并把 $L$ 和 $R$ 的坐標加上 $c_i$ 就行了.

最后合并到根之后，我們只有拐點的橫坐標，如何求出答案（也就是 $f_{1,L}$ ）呢？
注意到， $f_{1,0}$ 其實就是所有邊權之和，能很方便的求出來，又因為我們知道相鄰兩個端點的斜率差均為 $1$ ， $[L,R]$ 的斜率為 $0$ ，那么我們只需要倒著推一遍就行了.

代碼

#include<bits/stdc++.h> const int N=1e6+100; const int mod=1e9+7; #define ll long long using namespace std; inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m; int fa[N],fv[N],son[N]; int rt[N],tot,ls[N],rs[N],dis[N]; ll val[N]; int merge(int x,int y){//printf("merge x=%d y=%d\n",x,y);if(!x||!y) return x|y;if(val[x]<val[y]) swap(x,y);rs[x]=merge(rs[x],y);if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);dis[x]=dis[rs[x]]+1;return x; } inline int pop(int x){return merge(ls[x],rs[x]); } ll sum; void debug(int x){if(!x) return;printf("x=%d ls=%d rs=%d val=%lld\n",x,ls[x],rs[x],val[x]);debug(ls[x]);debug(rs[x]);return; } int main(){dis[0]=-1;n=read();m=read();for(int i=2;i<=n+m;i++){fa[i]=read();son[fa[i]]++;sum+=(fv[i]=read());}for(int i=n+m;i>=2;i--){ll l(0),r(0);//printf("i=%d\n",i);if(i<=n){while(--son[i]) rt[i]=pop(rt[i]);r=val[rt[i]];rt[i]=pop(rt[i]);l=val[rt[i]];rt[i]=pop(rt[i]);//printf("ok");}val[++tot]=l+fv[i];val[++tot]=r+fv[i];rt[i]=merge(rt[i],merge(tot-1,tot));//printf("OK rtfa=%d\n",rt[fa[i]]);printf("\ni=%d:\n",i);debug(rt[i]);rt[fa[i]]=merge(rt[fa[i]],rt[i]);}//debug(rt[1]);while(son[1]--){rt[1]=pop(rt[1]);//printf("\nrt=%d\n",rt[1]);}while(rt[1]){sum-=val[rt[1]];rt[1]=pop(rt[1]);//printf("\nrt=%d\n",rt[1]);}printf("%lld\n",sum); } /* 1 281239 */

總結

以上是生活随笔為你收集整理的P3642 [APIO2016]烟火表演（左偏树、函数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。