题解 | #最小连通代价#

最外层分四种情况，内层再加一种全奇全偶的情况；
当a，b都大于零时再分为a大和b大两种；
一共十种情况

void solve() {
    ll n, a, b; cin >> n >> a >> b;
    ll even=0,odd=0;
    for (ll i = 0; i < n; i++) {
        ll x; cin >> x;
        if (x & 1)odd++;
        else even++;
    }
    ll sum = odd + even,ans;
    if (a <= 0 && b <= 0) {
        ans = factorial(odd - 1) * a + factorial(even - 1) * a + odd * even * b;
    }
    else if (a <= 0 && b > 0) {
        ans = factorial(odd - 1) * a + factorial(even - 1) * a + b;
        if (odd == 0 || even == 0)ans-=b;
    }
    else if (a > 0 && b <= 0) {
        ans = odd * even * b;
        if (odd == 0 || even == 0)ans = a * (sum - 1);
    }
    else {
        if (a >= b) {
            ans = b * (sum - 1);
            if (odd == 0 || even == 0)ans = a * (sum - 1);
        }
        else {
            ans = a * (sum - 2) + b;
            if (odd == 0 || even == 0)ans = a * (sum - 1);
        }
    }
    cout << ans << endl;
}