【APIO2016】Fireworks【闵可夫斯基和】【凸包向量和】【可并堆】

题意：给一棵带边权的树，可以花费 $1$ 的代价把一条边的边权修改 $1$，一条边可以修改多次，求使得根到叶子距离相等的最小代价。

$n\le 3\times 10^5$

先暴力 dp

设 $f(u,k)$ 表示 $u$ 到子树内所有叶子距离为 $k$ 的最小代价。因为仍然有多种，所以最小是有意义的。

加入一个儿子 $v$ 后，设这条边长度为 $x$：

$$f(u,k)⟵f(u,k)+\min \{|i-x|+f(v,k-i)\}$$

发现这东西就是 $|x-i|$ 和 $f_v$ 做闵可夫斯基和，所以归纳法证明是个凸包。

然后 $|x-i|$ 这个东西相当于是一段 $(x,-x)$ 的向量和斜率为 $1$ 的一条射线，因为凸包斜率都是整数，相当于找到斜率为 $0$ 的这一段，将它和它右边的向右下分别移动 $x$,然后右边替换为斜率为 $1$ 的射线。

然后是后面的凸包向量和，我们按从大到小维护凸包的所有顶点的横坐标，并规定每经过一个点斜率会减小 $1$，显然最开始的斜率是 $1$。那么凸包向量和就是所有顶点的可重并集。（一个点出现两次说明斜率变化了 $2$）

用可并堆维护即可。最后得到了根的凸包，它的截距是所有边的和，然后就可以推出答案。

复杂度 $\mathrm{O}(n\log n)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <vector> #define MAXN 600005 using namespace std; typedef long long ll; 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; } int ch[MAXN][2],fa[MAXN],tot; ll val[MAXN]; int find(int x){return fa[x]==x? x:fa[x]=find(fa[x]);} int merge(int x,int y) {if (!x||!y) return x|y;if (val[x]<val[y]) swap(x,y);fa[ch[x][1]=merge(ch[x][1],y)]=x;swap(ch[x][0],ch[x][1]);return x; } inline void insert(int& x,int v){val[++tot]=v,x=merge(x,tot);} inline void erase(int& x){fa[ch[x][0]]=ch[x][0],fa[ch[x][1]]=ch[x][1],x=fa[x]=merge(ch[x][0],ch[x][1]);} vector<int> e[MAXN]; int c[MAXN],rt[MAXN]; void dfs(int u) {if (!e[u].size()) return insert(rt[u],c[u]),insert(rt[u],c[u]);for (int i=0;i<(int)e[u].size();i++){dfs(e[u][i]);rt[u]=merge(rt[u],rt[e[u][i]]);}for (int i=0;i<(int)e[u].size()-1;i++) erase(rt[u]);int x,y;x=rt[u],erase(rt[u]);y=rt[u],erase(rt[u]);val[x]+=c[u],val[y]+=c[u];ch[x][0]=ch[x][1]=ch[y][0]=ch[y][1]=0;fa[x]=x,fa[y]=y;rt[u]=merge(rt[u],x);rt[u]=merge(rt[u],y); } int main() {int n=read()+read();ll sum=0;for (int i=1;i<=n;i++) fa[i]=i;for (int i=2;i<=n;i++) e[read()].push_back(i),sum+=c[i]=read();dfs(1);int las=rt[1],k=0;while (rt[1]){erase(rt[1]);int cur=rt[1];sum-=k*(val[las]-val[cur]);las=cur,++k;}cout<<sum;return 0; }

总结

以上是生活随笔为你收集整理的【APIO2016】Fireworks【闵可夫斯基和】【凸包向量和】【可并堆】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。