题解 | 最小连通代价

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
    ll n,a,b;
    cin>>n>>a>>b;
    ll cnt0=0,cnt1=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(abs(x)%2)cnt1++;
        else cnt0++;
    }

    ll ans = 0;
    // cout<<cnt0<<' '<<cnt1<<endl;
    if(a<=0&&b<=0)
    {
        ans = (cnt0-1)*cnt0/2*a+(cnt1-1)*cnt1/2*a+cnt0*cnt1*b;
    }
    else if(a<=0)
    {
        ans = (cnt0-1)*cnt0/2*a+(cnt1-1)*cnt1/2*a;
        if(cnt0&&cnt1)ans+=b;
    }
    else if(b<=0)
    {
        ans = cnt0*cnt1*b;
        if(cnt0==0||cnt1==0)
        {
            ans = max(cnt0-1,cnt1-1)*a;
        }
    }
    else 
    {
        if(cnt0==0||cnt1==0)ans = (max(cnt0,cnt1)-1)*a;
        else
        {
            ll res1 = (n-2)*a+b;
            ll res2 = (n-1)*b;
            ans = min(res1,res2);
        }


    }
    cout<<ans<<endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

分类讨论即可