2019東北4省大会A.Apple Business

link
簡単な題意:1粒の(n)個の点の二叉木に、par[i]=i/2、各点に(a[i])個の果実があり、(m)回の操作があり、毎回(uto v)(保証(u)は(v)の祖先)の中で(c)個を超えない果実を取り、貢献(w)の収益を取る
まず暴力的にエッジを建てて費用を流すことができます.最適化を考慮すると、明らかな貪欲な戦略がある:(w)に従って大きい順から小さい順にできるだけ多く選択し、二分加二分図マッチングが可能であると判断する.
Hall定理を考慮すると,任意のサブセットに対する並列,(sum_{iin S}a[i]gesum_{u_iin S&v_iin S}c_i)に相当する.
明らかに私たちはこれが連結ブロックである場合を考慮する必要があります.(dp)が(i)をルートとする最小サブツリーを考慮する.
ルートが確定したので、(c_i)を(v_i)に割り当てることができます.
遷移は[f[i][j]=min(f[i*2][j],0)+min(f[i*2+1][j],0-0)+val[i][j]]前処理(nlog n)、1本のチェーンを挿入し、1本のチェーンを含む最小のインターフェースブロック複雑度(nlog^2 n)を算出する.
コード#コード#

#include
using namespace std;
const int N=2e5+5;
typedef long long ll;
long long f[20][N<<1],g[20][N<<1];
int dep[N],a[N];
int n,m;
ll ans=0;
struct Line{
    int u,v,cap,w;
    bool operator < (const Line b)const{return w < b.w;}
    void read(){scanf("%d%d%d%d",&u,&v,&cap,&w);}
}l[N];

void Main(){
    ans=0;
    cin >> n >> m;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        dep[i]=dep[i>>1]+1;
        for(int j=dep[i];j;j--)g[j][i]=a[i];
    }
    for(int i=1;i<=dep[n];i++){
        for(int j=n;j;j--)f[i][j]=min(0ll,f[i][j<<1|1])+min(0ll,f[i][j<<1])+g[i][j];
    }
    for(int i=1;i<=m;i++)l[i].read();
    sort(l+1,l+m+1);
    for(int i=m;i;i--){
        int hed=l[i].u;ll Mn=l[i].cap;
        for(;hed;hed>>=1){
            int d=dep[hed],nxt=l[i].v,lst=0;ll ths=0;
            while(nxt!=(hed>>1)){
                ths+=min(0ll,(nxt<<1|1)==lst?0ll:f[d][nxt<<1|1])+min(0ll,(nxt<<1)==lst?0ll:f[d][nxt<<1])+g[d][nxt];
                lst=nxt;nxt>>=1;
            }
            Mn=min(Mn, ths);
        }
        ans+=l[i].w*Mn;
        hed=l[i].u;
        for(;hed;hed>>=1){
            int nxt=l[i].v,d=dep[hed];
            g[d][nxt]-=Mn;
            for(;nxt;nxt>>=1){
                f[d][nxt]=min(0ll,f[d][nxt<<1])+min(0ll,f[d][nxt<<1|1])+g[d][nxt];
            }
        }
    }
    for(int d=1;d<=dep[n];d++)for(int i=1;i<=n;i++)f[d][i]=g[d][i]=0;
    cout << ans << endl;
}

int main()
{
    int T;cin >> T;
    while(T--){
        Main();
    }
    return 0;
}