lamps.cpp

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;

const int N = 34, oo = 1e9+7;
int n, T, col[N], orgCol[N];
vector<int> adj[N];

int CountChild[N], par[N], num;
vector<int> vec[N];

void DFS(int dad, int u) {
    CountChild[u] = 1; par[u] = dad;
    for (int v : adj[u]) if (v != dad) {
        DFS(u, v);
        CountChild[u] += CountChild[v];
    }
}

bool mark[N];
int root[N];

void DFS2(int dad, int u) {
    vec[num].push_back(u); mark[u] = true;
    for (int v : adj[u]) if (v != dad) DFS2(u, v);
}

int cutPoint = -1;

void prepare() {
    DFS(0, 1);

    for (int u = 1; u <= n; ++u) {
        bool ok = true;
        for (int v : adj[u]) {
            if (v == par[u] && n - CountChild[u] > n/2) { ok = false; break; }
            if (v != par[u] && CountChild[v] > n/2) { ok = false; break; }
        }
        if (ok) { cutPoint = u; mark[u] = true; break; }
    }

    for (int v : adj[cutPoint]) {
        if (par[v] == cutPoint) {
            ++num; DFS2(cutPoint, v);
            root[num] = v;
        }
    }

    root[++num] = par[cutPoint];
    for (int u = 1; u <= n; ++u) if (!mark[u]) vec[num].push_back(u), mark[u] = true;
    if (vec[num].empty()) --num;
}

vector<int> ls;
int belong[N];
int type0[N], type1[N], save0[N], save1[N];

bool BIT(int n, int k) { return n & (1<<k); }

void calc(int id) {
    ls = vec[id]; int sz = ls.size();

    for (int mask = 0; mask < (1<<sz); ++mask) {
        for (int i = 0; i < sz; ++i) col[ls[i]] = orgCol[ls[i]];

        int step = 0, ok = 0;
        for (int i = 0; i < sz; ++i) if (BIT(mask, i)) {
            ++step; int u = ls[i];
            if (u == root[id]) ok = 1;
            for (int v : adj[u]) if (belong[v] == id) col[v] = 1 - col[v];
            col[u] = 1 - col[u];
        }

        for (int u : ls) if (col[u] == 1) { step = -1; break; }
        if (step == -1) continue;

        if (!ok && type0[id] > step) { type0[id] = step; save0[id] = mask; }
        if ( ok && type1[id] > step) { type1[id] = step; save1[id] = mask; }
    }
}

int res;
bool cc;
vector<ii> ans, diff, tmpAns;

void process(int Add) {
    for (int i = 1; i <= num; ++i) type0[i] = type1[i] = oo, save0[i] = save1[i] = -1;
    for (int i = 1; i <= num; ++i) {
        calc(i);
        if (type0[i] == oo && type1[i] == oo) return;
    }

    int tmpRes = 0; tmpAns.clear(); col[cutPoint] = orgCol[cutPoint];
    for (int i = 1; i <= num; ++i) {
            //assert(type1[i] != oo || type0[i] != oo);
        if (type1[i] == oo) tmpRes += type0[i], tmpAns.push_back(ii(save0[i], i));
        if (type0[i] == oo) {
            tmpRes += type1[i], tmpAns.push_back(ii(save1[i], i));
            col[cutPoint] = 1 - col[cutPoint];
        }
    }

    diff.clear();
    for (int i = 1; i <= num; ++i) if (type1[i] != oo && type0[i] != oo)
        diff.push_back(ii(type1[i] - type0[i], i));

    int l = 0, r = 0;
    while (r < (int) diff.size() && diff[r].first <= 0) ++r; --r;

    if (col[cutPoint] == 0) {
        if ( (r - l + 1) % 2 == 1 ) --r;
        for (int i = l; i <= r; ++i) {
            tmpRes += type1[diff[i].second];
            tmpAns.push_back(ii(save1[diff[i].second], diff[i].second));
        }
        for (int i = r+1; i < (int) diff.size(); ++i) {
            tmpRes += type0[diff[i].second];
            tmpAns.push_back(ii(save0[diff[i].second], diff[i].second));
        }
    }
    else {
        if ( (r - l + 1) % 2 == 0 ) --r;
        if (l > r) ++r;
        for (int i = l; i <= r; ++i) {
            tmpRes += type1[diff[i].second];
            tmpAns.push_back(ii(save1[diff[i].second], diff[i].second));
        }
        for (int i = r+1; i < (int) diff.size(); ++i) {
            tmpRes += type0[diff[i].second];
            tmpAns.push_back(ii(save0[diff[i].second], diff[i].second));
        }
    }

    if (res > tmpRes + Add) {
        res = tmpRes + Add;
        ans = tmpAns;
        if (Add == 1) cc = true;
        else cc = false;
    }
}

void sol() {
    for (int i = 1; i <= num; ++i) for (int u : vec[i]) belong[u] = i;

    res = oo; ans.clear(); cc = false;

    /// not change cutPoint
    process(0);

    /// change cutPoint
    for (int v : adj[cutPoint]) orgCol[v] = 1 - orgCol[v]; orgCol[cutPoint] = 1 - orgCol[cutPoint];
    process(1);

    /// Print
    if (res == oo) { cout << -1 << '\n'; return; }

    cout << res << " ";
    if (cc) cout << cutPoint << " ";
    for (int i = 0; i < (int) tmpAns.size(); ++i) {
        int id = tmpAns[i].second, mask = tmpAns[i].first;
        for (int bit = 0; bit < (int) vec[id].size(); ++bit) if (BIT(mask, bit)) {
            cout << vec[id][bit] << " ";
        }
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("LAMPS.inp", "r", stdin);
    freopen("LAMPS.out", "w", stdout);

    cin >> n >> T;
    int u, v;
    for (int i = 1; i < n; ++i) {
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }

    prepare();

    while (T--) {
        for (int i = 1; i <= n; ++i) cin >> orgCol[i], orgCol[i] = 1 - orgCol[i];

        sol();
    }

    return 0;
}