题目
一棵树,(n)个非叶子节点，编号为(1-n)，(m)个叶子节点，编号为(n+1-n+m)
每条边有边权，修改边权的代价为(|a-b|) ;
定义一个叶子的距离为到1(根节点)的边的长度之和；
求最小的修改代价使得最后所有叶子的距离相同；
$1 le M le 300000 $
题解
(做完这个题之后有一种为什么uoj的好评只能点一次的遗憾)
-
设(f(x))表示最终距离为(x)的答案，对于叶子是下凸的并且每段都是一次函数，归纳都满足这个性质的并设最值的区间为([L,R]) ，注意到这一段的(f'_u)为0，左边<=-1，右边>=1，考虑转移:
[f_u(x) = sum_{v} min_{k=0}^x { f_v(x-k) + |w-k| } \ 考虑单个的v:\ f_u(x) = egin{cases} f_v(x) + w & x le L \ f_v(L) + w-(x-L) & L lt x le L+w \ f_v(L) & L+w lt x le R+w \ f_v(R) + (x-R)-w & R+w lt x \ end{cases} \也即把[0,L]向上平移w个单位，[L,R]向右移动w个单位； \中间用斜率为-1的线连接,再从R+w作一条斜率为1的射线； \所有v相加仍然是凸的 ]这里有详细的说明，不过建议自己脑补一下
-
斜率是连续的，设交点横坐标分别为(x_m,x_m-1,cdots,x_１,cdots)， $ x_i $ 的左边斜率 $ =-i $ ，规定(x_{m+1})为(0)
[ans = f_1(0) + sum_{i=1}^{m}-i(x_i-x_{i+1}) = f_1(0) + sum_{i=1}^{m} -x_i \ f_1(0)=sum w ] -
维护交点，所有(f_v)相加即交点集合合并，可以知道此时最大的斜率为(|v|-1)直接再删除那么多个交点即可；
-
用可并堆维护，我写的左偏树;
#include<bits/stdc++.h> #define ll long long #define mk make_pair #define pb push_back #define fi first #define se second using namespace std; const int N=600010; int n,m,ls[N],rs[N],rt[N],sz,ds[N]; ll wv[N]; typedef pair<int,int>pii; vector<pii>g[N]; bool cmp(int a,int b){return wv[a]==wv[b]?a<b:wv[a]<wv[b];} char gc(){ static char*p1,*p2,s[1000000]; if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); return(p1==p2)?EOF:*p1++; } int rd(){ int x=0;char c=gc(); while(c<'0'||c>'9')c=gc(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc(); return x; } int merge(int x,int y){ if(!x||!y)return x+y; if(cmp(x,y))swap(x,y); rs[x]=merge(rs[x],y); if(ds[ls[x]]<ds[rs[x]])swap(ls[x],rs[x]); ds[x]=ds[rs[x]]+1; return x; } int main(){ // freopen("fireworks.in","r",stdin); // freopen("fireworks.out","w",stdout); ll ans=0;n=rd();m=rd(); for(int i=2;i<=n+m;++i){ int u=rd(),w=rd(); g[u].pb(mk(i,w)); ans+=w; } for(int i=n+1;i<=n+m;++i)rt[i]=++sz,rs[rt[i]]=++sz; for(int i=n;i;--i){ int d=(int)g[i].size(); for(int j=0;j<d;++j){ int v=g[i][j].fi,w=g[i][j].se; wv[rt[v]]+=w; if(cmp(ls[rt[v]],rs[rt[v]]))wv[rs[rt[v]]]+=w; else wv[ls[rt[v]]]+=w; rt[i]=merge(rt[i],rt[v]); } for(int j=1;j<d;++j)rt[i]=merge(ls[rt[i]],rs[rt[i]]); } rt[1]=merge(ls[rt[1]],rs[rt[1]]); while(rt[1]){ ans-=wv[rt[1]]; rt[1]=merge(ls[rt[1]],rs[rt[1]]); } cout<<ans<<endl; return 0; }