CEOI '20 - Spring cleaning

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;

// Segment tree
class Node {
private:
    int even = 0, odd = 0;
    bool prop = false;
    Node * left, * right;
    void propagate(int l, int r) {
        int mid = (l + r) / 2;
        if (!left) left = new Node(), left->even = mid-l;
        if (!right) right = new Node(), right->even = r-mid;
        if (prop) {
            left->prop = !left->prop;
            swap(left->even, left->odd);
            right->prop = !right->prop;
            swap(right->even, right->odd);
            prop = false;
        }
    }
public:
    void rangeToggle(int l, int r, int ql, int qr) { // flips even and odd nodes in a range
        if (qr <= l || r <= ql) return;
        else if (ql <= l && r <= qr) {
            prop = !prop;
            swap(even, odd);
        } else {
            propagate(l, r);
            int mid = (l + r) / 2;
            left->rangeToggle(l, mid, ql, qr);
            right->rangeToggle(mid, r, ql, qr);
            even = left->even + right->even;
            odd = left->odd + right->odd;
        }
    }
    int rangeEven(int l, int r, int ql, int qr) { // counts number of even in a range
        if (qr <= l || r <= ql) return 0;
        else if (ql <= l && r <= qr) return even;
        else {
            propagate(l, r);
            int mid = (l + r) / 2;
            return left->rangeEven(l, mid, ql, qr) + right->rangeEven(mid, r, ql, qr);
        }
    }
};

// HLD
vector<int> hldIndex, head, subtree, par;
void getSubtree(int node, int parent = 0) {
    par[node] = parent;
    subtree[node] = 1;
    for (int child : g[node]) {
        if (child == parent) continue;
        getSubtree(child, node);
        subtree[node] += subtree[child];
    }
}
int nextAvailableIndex = 0;
void build(int node, int hd, int parent = 0) {
    hldIndex[node] = nextAvailableIndex++;
    head[node] = hd;

    if (g[node].size() == 1 && parent) return;
    int mx = 0;
    if (g[node][0] == parent) mx = 1;
    for (int i = mx+1; i < (int)g[node].size(); ++i) {
        if (g[node][i] == parent) continue;
        if (subtree[g[node][i]] > subtree[g[node][mx]]) mx = i;
    }
    // move mx to front
    while (mx) {
        swap(g[node][mx], g[node][mx-1]);
        --mx;
    }
    // continue dfs as usual
    build(g[node].front(), hd, node);
    for (size_t i = 1; i < g[node].size(); ++i) {
        if (g[node][i] != parent) build(g[node][i], g[node][i], node);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    g.resize(1+n);
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int root = 1; // choose non-leaf root
    while (g[root].size() == 1) ++root;

    // build HLD
    subtree.resize(1+n), par.resize(1+n);
    getSubtree(root);
    hldIndex.resize(1+n), head.resize(1+n);
    build(root, root);


    Node * segRoot = new Node(); // segment tree for HLD
    auto toggleToRoot = [&](int a) { // toggle path from a to root
        while (a) {
            int first = hldIndex[head[a]], last = hldIndex[a]; // inclusive
            segRoot->rangeToggle(0, n, first, last+1); // toggle segtree range [first, last]
            a = par[head[a]];
        }
    };
    int originalLeaves = 0;
    for (int i = 1; i <= n; ++i) {
        if (g[i].size() == 1) {
            ++originalLeaves;
            toggleToRoot(i);
        }
    }

    while (q--) {
        int D; cin >> D;
        vector<int> a(D);
        for (int &x : a) cin >> x;

        int totalLeaves = originalLeaves + D;
        sort(a.begin(), a.end());
        vector<int> noLongerLeaves;
        for (size_t i = 0; i < a.size(); ++i) {
            if (g[a[i]].size() == 1 && (!i || a[i] != a[i-1])) {
                --totalLeaves;
                noLongerLeaves.push_back(a[i]);
            }
        }
        if (totalLeaves & 1) {
            cout << "-1\n";
            continue;
        }

        for (int &x : a) toggleToRoot(x);
        for (int &x : noLongerLeaves) toggleToRoot(x);

        int even = segRoot->rangeEven(0, n, 1, n); // query number of nodes that have an even number of leaves in their subtree
        cout << (n+D-1) + even << '\n'; // cost is 1 on every odd edge, 2 on every even edge

        for (int &x : a) toggleToRoot(x);
        for (int &x : noLongerLeaves) toggleToRoot(x);
    }
    return 0;
}