给出一棵树，边有边权，可以花费1的代价把一条边的权值加1或者1，不能减到负的。 要让根到所有叶子的边权和都相等。问最小代价。 n<=600000
设 fx(i) f x ( i ) 表示 x x 的子树中的叶子到 xx 距离全部搞成 i i 的最小代价。 设 gx(i) g x ( i ) 表示 x x 的子树中的叶子到 faxfax 的距离全部搞成 i i 的最小代价。 那么有dp方程： fx(i)=∑y∈sonxgy(i)fx(i)=∑y∈sonxgy(i)
gx(i)=minδ≥−axfx(i−ax−δ)+|δ| g x ( i ) = min δ ≥ − a x f x ( i − a x − δ ) + | δ |直接dp是 O(n2) O ( n 2 ) 的，考虑优化。 注意 fx(i)，gx(i) f x ( i ) ， g x ( i ) 是关于的一条线性下凸折线，证明可以考虑从叶子是线性下凸折线开始往上推。
考虑 gx g x 是如何从 fx f x 转变的。 先是由 fx f x 整体右移 ax a x 。 δ δ 是没有上界的，相当于右边都能从左边更新，根据dp方程，直接把最右侧斜率 ≥2 ≥ 2 的部分都扔掉就行了。 δ δ 有个下界，相当于 i i 可以从 ≤i ax≤i ax 的范围内更新，画图观察可以发现就是把斜率 ≤−1 ≤ − 1 的部分往平移了向量 (−ax,ax) ( − a x , a x ) 。
fx f x 就是把所有儿子的折线合并。
如果我们维护的是折线拐点的横坐标，设 x x 有 cntcnt 个儿子，斜率 ≥2 ≥ 2 的拐点就有 cnt−1 c n t − 1 个，删除后就只有斜率为0和1的拐点坐标增加了 ax a x 。
以上操作都可以用可并堆维护，时间复杂度为 O(nlogn) O ( n l o g n ) 。
最后如何计算答案？注意到 f1(0)=∑ai f 1 ( 0 ) = ∑ a i ，再把拐点从左到右计算一下就可得到折线最小值了。
#include<bits/stdc++.h> #define ll long long using namespace std; int getint() { int i=0,f=1;char c; for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar()); if(c=='-')c=getchar(),f=-1; for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0'; return i*f; } const int N=6e5+5; ll sum,v[N]; int n,m,fa[N],w[N],son[N]; int tot,rt[N],l[N],r[N]; int merge(int x,int y) { if(!x||!y)return x+y; if(v[x]<v[y])swap(x,y); r[x]=merge(r[x],y); swap(l[x],r[x]); return x; } int pop(int x){return merge(l[x],r[x]);} void dfs(int x) { if(!x)return; sum-=v[x]; dfs(l[x]),dfs(r[x]); } int main() { //freopen("lx.in","r",stdin); n=getint(),m=getint(); for(int i=2;i<=n+m;i++) { fa[i]=getint(),w[i]=getint(); sum+=w[i],son[fa[i]]++; } for(int i=n+m;i>1;i--) { ll L=0,R=0; if(son[i]) { while(--son[i])rt[i]=pop(rt[i]); R=v[rt[i]],rt[i]=pop(rt[i]); L=v[rt[i]],rt[i]=pop(rt[i]); } v[++tot]=L+w[i],v[++tot]=R+w[i]; rt[i]=merge(rt[i],merge(tot,tot-1)); rt[fa[i]]=merge(rt[fa[i]],rt[i]); } while(son[1]--)rt[1]=pop(rt[1]); dfs(rt[1]);cout<<sum<<'\n'; return 0; }