Submission #1350960

#TimeUsernameProblemLanguageResultExecution timeMemory
1350960msab3fSpring cleaning (CEOI20_cleaning)C++20
100 / 100
146 ms30680 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100'000 + 10;
const int MAX_LG = 17;

int n, q, r, st[MAX_N], ft[MAX_N], h[MAX_N], par[MAX_N][MAX_LG], odds[MAX_N][MAX_LG], base;
vector<int> adj[MAX_N];

int vpar[MAX_N];
vector<int> vadj[MAX_N];
bool dp[MAX_N];

void dfs(int u, int p) {
    static int time = 0;
    st[u] = time++;
    if (adj[u].size() == 1) {
        odds[u][0] = 1;
    }
    for (int v : adj[u]) {
        if (v != p) {
            h[v] = h[u] + 1;
            par[v][0] = u;
            dfs(v, u);
            odds[u][0] ^= odds[v][0];
        }
    }
    if (u != r && odds[u][0] == 0) {
        ++base;
    }
    ft[u] = time;
}

int get_lca(int u, int v) {
    if (h[u] < h[v]) swap(u, v);
    for (int i = 0, diff = h[u] - h[v]; diff != 0; ++i, diff >>= 1) {
        if (diff & 1) u = par[u][i];
    }
    if (u == v) return u;
    for (int i = MAX_LG - 1; i >= 0; --i) {
        if (par[u][i] != par[v][i]) {
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

int get_odds(int u, int k) {
    int res = 0;
    for (int i = 0; k != 0; ++i, k >>= 1) {
        if (k & 1) {
            res += odds[u][i];
            u = par[u][i];
        }
    }
    return res;
}

void vdfs(int u) {
    for (int v : vadj[u]) {
        vdfs(v);
        dp[u] ^= dp[v];
    }
}

int main() {
    cin >> n >> q;

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

    r = 1;
    while (adj[r].size() == 1) ++r;

    dfs(r, -1);

    for (int i = 1; i < MAX_LG; ++i) {
        for (int u = 1; u <= n; ++u) {
            par[u][i] = par[par[u][i - 1]][i - 1];
            odds[u][i] = odds[u][i - 1] + odds[par[u][i - 1]][i - 1];
        }
    }

    while (q--) {
        int d;
        cin >> d;
        vector<int> V = {r};
        for (int i = 0; i < d; ++i) {
            int v;
            cin >> v;
            dp[v] ^= 1;
            V.push_back(v);
        }
        static auto cmp = [&] (int u, int v) { return st[u] < st[v]; };
        sort(V.begin(), V.end(), cmp);
        V.erase(unique(V.begin(), V.end()), V.end());
        for (int i = int(V.size()) - 2; i >= 0; --i) {
            V.push_back(get_lca(V[i], V[i + 1]));
        }
        sort(V.begin(), V.end(), cmp);
        V.erase(unique(V.begin(), V.end()), V.end());
        for (int i = 1; i < V.size(); ++i) {
            vpar[V[i]] = V[i - 1];
            while (ft[vpar[V[i]]] < ft[V[i]]) {
                vpar[V[i]] = vpar[vpar[V[i]]];
            }
            vadj[vpar[V[i]]].push_back(V[i]);
            if (adj[V[i]].size() == 1) {
                dp[V[i]] ^= 1;
            }
        }
        vdfs(r);
        if (odds[r][0] ^ dp[r]) {
            cout << -1 << '\n';
        } else {
            int res = n + d - 1 + base;
            for (int v : V) {
                if (v == r || !dp[v]) continue;
                res += 2 * get_odds(v, h[v] - h[vpar[v]]) - (h[v] - h[vpar[v]]);
            }
            cout << res << '\n';
        }
        for (int v : V) {
            vpar[v] = 0;
            vadj[v].clear();
            dp[v] = 0;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...