Solution of https://codeforces.com/contest/1330/problem/E

sol.cc

/*
    First I try to figure out what are the elements from 1 to 2 ** g - 1. In the end the value at node i(val[i]) is the following:

    - If i > 2 ** g - 1 then 0
    - If it isn't than the minimal value from it's subtree such that it's bigger than max(val[2 * i], val[2 * i + 1]) that is the value of the roots of its subtrees since the heap property is preserved
      during the operations.

    Since we know which values should be in the heap in the end and since calling f on an index means removing the associated value we call f on the indices whose value we don't need(all values are different) back
    to front. And that's it.
*/

#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
#define FOR(i, j, k, in) for (int i = j; i < k; i += in)
#define RFOR(i, j, k, in) for (int i = j; i >= k; i -= in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)

void merge_two(const vector<ll> &first, const vector<ll> &second, ll i1, ll i2, vector<ll> &res) {
    ll s1 = first.size(), s2 = second.size();

    while (i1 < s1 && i2 < s2) {
        if (first[i1] < second[i2])
            res.push_back(first[i1++]);
        else
            res.push_back(second[i2++]);
    }
    while (i1 < s1) res.push_back(first[i1++]);
    while (i2 < s2) res.push_back(second[i2++]);
}

void merge_three(const vector<ll> &first, const vector<ll> &second, const vector<ll> &third, vector<ll> &res) {
    ll i1 = 0ll, i2 = 0ll, i3 = 0ll;
    ll s1 = first.size(), s2 = second.size(), s3 = third.size();

    while (i1 < s1 && i2 < s2 && i3 < s3) {
        if (first[i1] < second[i2]) {
            if (third[i3] < first[i1])
                res.push_back(third[i3++]);
            else
                res.push_back(first[i1++]);
        } else {
            if (third[i3] < second[i2])
                res.push_back(third[i3++]);
            else
                res.push_back(second[i2++]);
        }
    }

    if (i1 == s1)
        merge_two(second, third, i2, i3, res);
    else if (i2 == s2)
        merge_two(first, third, i1, i3, res);
    else
        merge_two(first, second, i1, i2, res);
}

vector<ll> rec_solve(const vector<ll> &ais, ll curr, ll lower, ll upper, vector<ll> &min_val) {
    if (2 * curr > upper) {
        min_val[curr] = 0ll;
        return {ais[curr]};
    }

    auto left = rec_solve(ais, 2ll * curr, lower, upper, min_val);
    auto right = rec_solve(ais, 2ll * curr + 1, lower, upper, min_val);
    vector<ll> curr_vec(1, ais[curr]);
    vector<ll> ret;
    merge_three(left, right, curr_vec, ret);

    if (curr <= lower) {
        for (const auto el : ret) {
            if (el > max(min_val[2 * curr], min_val[2 * curr + 1])) {
                min_val[curr] = el;
                break;
            }
        }
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    vector<ll> p2(21, 1ll);
    FOR(i, 1, 21, 1)
    p2[i] = p2[i - 1] << 1ll;
    while (t--) {
        ll h, g;
        cin >> h >> g;
        ll upper = p2[h] - 1, lower = p2[g] - 1;
        vector<ll> ais(upper + 1);
        FOR(i, 1, upper + 1, 1)
        cin >> ais[i];
        vector<ll> min_val(upper + 1, 0);
        rec_solve(ais, 1ll, lower, upper, min_val);
        unordered_set<ll> needed;
        ll total = 0ll;
        FOR(i, 1, lower + 1, 1) {
            needed.insert(min_val[i]);
            total += min_val[i];
        }
        cout << total << endl;
        vector<ll> steps;
        RFOR(i, upper, 1, 1) {
            if (needed.find(ais[i]) == needed.end()) steps.push_back(i);
        }
        for (const auto step : steps) cout << step << " ";
        cout << endl;
    }

    return 0;
}