【loj2568】【APIO2016】【学习笔记 左偏树】烟花表演

题目

一棵树,\(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) = \begin{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;
  }

【loj2568】【APIO2016】【学习笔记 左偏树】烟花表演

原文：https://www.cnblogs.com/Paul-Guderian/p/10841237.html