「C.E.L.U-03」重构 题解

· · 题解

看着没有人用 wqs 二分做，就写一篇题解吧。

首先，通过 Prufer 序列，我们知道，对于任意一个长度为 n 的序列 d 满足 d_i\in [1,n-1],\sum d=2n-2，都能构建一棵树。

也就是说题目转化成了：

给定长为 n 的序列 v，构造长为 n 的序列 d 满足 d_i\in [1,n-1],\sum d=2n-2，最小化 \sum d_i^2v_i 的值。

直接 dp 肯定是不行的，复杂度不能接受。

观察到有 \sum d=2n-2 的限制，处理这种限制的利器就是 wqs 二分。

:::info[wqs 二分的实现]{open} 二分每个度数的惩罚值 t。对于每个 i，将 d_i 设为满足 d_i\in[1,n-1] 且使 d_i^2v_i-td_i 取到最小值的 d_i（可以使用二次函数的知识求出），然后根据 \sum d 与 2n-2 的大小关系调整 t。 :::

:::info[凸性的感性证明]{open} 因为答案是关于每个 d_i 的二次函数之和，随着 \sum d 的增大，答案的增加速度会越来越快，所以有凸性。 :::

:::success[代码]

#include<bits/stdc++.h>
#define int __int128
using namespace std;
typedef long long ll;
int n,a[300010];
int f[300010],cnt[300010];
int w(int as,int x,int at){
    return (as*x-at)*x;
}
void re(int &x){
    if(x<=1) x=1;
    if(x>=n-1) x=n-1;
}
int read(){
    ll x;
    cin>>x;
    return x;
}
void pr(int x){
    ll y=x;
    cout<<y<<" ";
}
int div(int x,int y){
    int p=(x%y+y)%y;
    x-=p;
    return x/y;
}
void ret(int at){
    memset(f,0,sizeof(f));
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++){
        int u=div(at,2*a[i]);
        int v=u+1;
        re(u);
        re(v);
        int uc=w(a[i],u,at);
        int vc=w(a[i],v,at);
        if(vc<=uc){
            f[i]=f[i-1]+vc;
            cnt[i]=cnt[i-1]+v;
        }
        else{
            f[i]=f[i-1]+uc;
            cnt[i]=cnt[i-1]+u;
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    int le=-1e9,ri=1e9,mid;
    while(le<ri){
        mid=(le+ri)>>1;
        ret(mid);
        if(cnt[n]>=2*n-2) ri=mid;
        else le=mid+1;
    }
    ret(le);
    pr(f[n]+(2*n-2)*le);
}

:::