P3642 APIO2016 煙火表演 可並堆

2022-09-22 21:31:35 字數 2385 閱讀 5785

戳這裡

這題是 zjoi2007時態同步 的加強版,那個題裡面只能加邊不能刪邊,而這個題允許刪邊

我們還是按照時態同步的想法來做,就是樹上dp,我們令 \(f(i,j)\) 表示使 \(i\) 的子樹內所有葉子節點到 \(i\) 的距離為 \(j\) 的最小代價,我們分析可以發現,

\(f(i,j)\) 是關於 \(i\) 的一個分段函式

分段區間的每一段區間一定是通過修改固定邊數條路徑,所以這一段分段函式的斜率就是修改路徑的條數

\(f(i,j)\) 是一個下凸殼

感性理解:一定存在一個區間 \(l,r\) 使得 \(\forall x \ 滿足f(i,l)\le f(i,x)\),那麼 \(x\le l\) 時需要大量刪邊導致代價增大, \(x\ge r\) 時需要大量加邊導致代價增大

由於樹形dp需要將兒子的 貢獻傳遞給父親,那麼我們現在考慮怎麼將兒子的貢獻累加到父親上,

記關於兒子的分段函式為 \(f()\) ,關於父親的分段函式為 \(g()\) , 兒子的斜率為 \(0\) 的區間(即代價最小的區間)為 \(l,r\) , 連線的邊的權值為 \(w\) , 記 \(x\) 為轉移到父親的距離,根據定義 \(g(x)=min_^(f(y)+|w-(x-y)|)\)

分類討論:

\(x\le l\) 時 由於 \(y\le x\) 所以 \(y< l\) ,即 \(f(y)\) 此時的斜率都小於等於 \(-1\) ,轉移 $ 1$ 距離的代價都大於等於 \(1\) ,那麼 \(y\) 取值越靠近 \(x\) 花費越少 ,所以當 \(y=x\) 時 \(g(x)=f(x)+w\)

\(l\le x\le l+w\) 當 \(y\ge l\) 時斜率為 \(0\) ,那麼修改不影響代價,此時 \(y\) 越小 \(|w-(x-y)|\) 越小 總代價越小,所以我們儘可能從 \(l\) 轉移過來 \(g(x)=f(l)+w-(x-l)\)

\(l+w\le x \le r+w\) 此時不用對 \(w\) 做任何增刪就能直接從 \(l,r\) 轉移過來,所以 \(g(x)=f(l)\)

\(r+w\le x\) 和 1 同理,由於此時 \(f(y)\) 的斜率都大於等於 \(1\) 所以轉移 \(1\) 距離的代價都大於等於 \(1\),那麼儘可能使得 \(y\) 斜率趨近 \(0\) 所以 \(g(x)=f(r)+(x-r)-w\)

我們得到了轉移式如下

\[g(x) = \begin f(x)+w & x \le l \\ f(l)+w-(x-l) & l < x < l+w \\ f(l) & l+w

我們觀察幾何意義可以發現

\([\ 0,l\ ]\) 向上平移 \(w\) 個單位長度 \([l,l+w\ ]\) 插入一條斜率為 \(-1\) 的線段 \([\ l,r\ ]\) 向右平移 \(w\) 個單位長度, \([r+w, \inf ]\) 插入一條斜率為 \(1\) 的線段

由於兩個凸殼合併時會使得斜率增加 ,所以我們用一個小 \(trick\) 來維護凸殼,那就是記一下拐點的座標,這樣任意兩個拐點之間的斜率就是 \(1\) (如果某個斜率不存在,我們只需要在同一個點多存幾個斜率,直到這個斜率存在),那再回頭看我們的轉移式,由於每一次轉移會使得新的凸殼右半部分斜率加 \(1\) 所以右側的拐點數等於兒子個數,而我們要做的就是每一次彈出斜率大於 \(0\) 的點,直到找到斜率為 \(0\) 的區間 \([l,r]\) ,刪除 \(r\) 點,插入 \(l+w,r+w\) 這樣 \([l,l+w]\) 這段斜率順便也變成了 \(-1\)

最後怎麼計算答案那,我們只需要找到 \(1\) 節點對應的 \([l,r]\) 區間,由於 每一次合併都會使得 \([0,l]\) 區間向上移一條邊權,所以 \(1\) 節點 \(f(0)=\sum w_i\) 然後直接刪掉斜率小於 \(0\) 的拐點,輸出 \([l,r]\) 區間的值

#includeusing namespace std;

namespace zzc

while (isdigit(ch))

return x*f; }

const int maxn = 3e5+5;

int n,m,tot;

long long ans,val[maxn<<1];

int fa[maxn],deg[maxn],dis[maxn<<1],lc[maxn<<1],rc[maxn<<1],w[maxn],rt[maxn];

int new_node(long long x)

int merge(int x,int y)

while(deg[1]--) pop(rt[1]);

while(rt[1]) ans-=val[rt[1]],pop(rt[1]);

printf("%lld\n",ans); }}

int main()