題意：給一棵 $n$ 個點的有點權(quán)的樹，你需要找 $k$ 條根到葉子的路徑，使得路徑并集的權(quán)值和最大。

$n\le 2\times 10^5$

其實就是個貪心，只是從這個角度更自然一點(

先有個顯然的 dp，設(shè) $f(u,k)$ 為從 $u$ 往下找 $k$ 條鏈覆蓋的權(quán)值最大值。

$$f^{\prime }(u,k)=\underset{i=0}{\overset{k}{\max }}\{f(u,i)+f(v,k?i)\}+[k>0]a_u$$

發(fā)現(xiàn)是個閔可夫斯基和的形式。

然后往這個方向考慮，不管怎么理解都能看出這是個凸殼。

所以合并的時候繼承葉子最多的兒子（或者直接繼承子樹最大的也可以）的凸包，其他的暴力做閔可夫斯基和。可以用堆來維護(hù)斜率也就是差分，然后暴力插入。最后把第一項 $+a_u$ 即可。

復(fù)雜度是 $\mathrm{O}(n{\log }^{2}n)$，但常數(shù)很小。

腦抽寫了個平衡樹，我是 SB

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #include <cstdlib> #define MAXN 200005 using namespace std; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } typedef long long ll; int ch[MAXN][2],key[MAXN],tot; ll val[MAXN]; inline int newnode(int v){return val[++tot]=v,key[tot]=rand(),tot;} int merge(int x,int y) {if (!x||!y) return x|y;if (key[x]<key[y]) return ch[x][1]=merge(ch[x][1],y),x;return ch[y][0]=merge(x,ch[y][0]),y; } void split(int x,ll v,int& l,int& r) {if (!x) return (void)(l=r=0);if (val[x]>v) split(ch[x][1],v,l,r),ch[x][1]=l,l=x;else split(ch[x][0],v,l,r),ch[x][0]=r,r=x; } int getfir(int& x) {if (!ch[x][0]) {int t=x;x=ch[x][1],ch[t][1]=0;return t;}return getfir(ch[x][0]); } inline void insert(int& x,int v) {int l,r;split(x,val[v],l,r);x=merge(merge(l,v),r); } vector<int> e[MAXN]; int a[MAXN],rt[MAXN],lev[MAXN],son[MAXN]; void dfs(int u) {if (e[u].empty()) return (void)(lev[u]=1);for (int i=0;i<(int)e[u].size();i++){dfs(e[u][i]);if (lev[e[u][i]]>lev[son[u]]) son[u]=e[u][i];lev[u]+=lev[e[u][i]];} } void Dfs(int u) {if (son[u]) Dfs(son[u]),rt[u]=rt[son[u]];else return (void)(rt[u]=newnode(a[u]));for (int i=0;i<(int)e[u].size();i++)if (e[u][i]!=son[u]){Dfs(e[u][i]);while (rt[e[u][i]]) insert(rt[u],getfir(rt[e[u][i]]));}int p=getfir(rt[u]);val[p]+=a[u];rt[u]=merge(p,rt[u]); } int main() {int n,k;n=read(),k=read();for (int i=1;i<=n;i++) a[i]=read();for (int i=1;i<n;i++){int u,v;u=read(),v=read();e[u].push_back(v);}dfs(1),Dfs(1);ll ans=0;while (k--) ans+=val[getfir(rt[1])];cout<<ans;return 0; }

總結(jié)

以上是生活随笔為你收集整理的【BZOJ3252】攻略【闵可夫斯基和】【堆启发式合并】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。