제출 #1361835

#제출 시각아이디문제언어결과실행 시간메모리
1361835HishamAlshehriSpring cleaning (CEOI20_cleaning)C++20
100 / 100
108 ms33076 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

constexpr int maxn = 400001;
int n, q, d[maxn], in[maxn], jump[18][maxn], parity[maxn], prf[maxn], tim, ans;
vector<int> adj[maxn], vrt[maxn];
bool vis[maxn], markNode[maxn];
int addcnt[maxn];

int dfs(int v) {
    in[v] = tim++;
    vis[v] = 1;
    int num = 0;

    if ((int)adj[v].size() == 1) num = 1;

    for (int u : adj[v]) {
        if (!vis[u]) {
            jump[0][u] = v;
            d[u] = d[v] + 1;
            int x = dfs(u);
            ans += x;
            num += x;
        }
    }

    parity[v] = (num % 2 ? 1 : -1);
    return 2 - num % 2;
}

void calc(int v, int cur) {
    vis[v] = 1;
    prf[v] = cur;

    for (int u : adj[v]) if (!vis[u]) calc(u, cur + parity[u]);
}

int rt;

void build() {
    jump[0][rt] = rt;
    for (int i = 1; i < 18; i++) {
        for (int j = 1; j <= n; j++) jump[i][j] = jump[i - 1][jump[i - 1][j]];
    }
}

int lca(int v, int u) {
    if (v == u) return v;
    if (d[v] > d[u]) swap(u, v);

    int t = d[u] - d[v];

    for (int k = 17; k >= 0; k--) {
        if (((1LL << k) & t)) u = jump[k][u];
    }

    if (v == u) return v;

    for (int k = 17; k >= 0; k--) {
        if (jump[k][v] != jump[k][u]) v = jump[k][v], u = jump[k][u];
    }

    return jump[0][v];
}

int cnt;

int solve_vtree(int v) {
    int odd = markNode[v];
    for (int u : vrt[v]) {
        int x = solve_vtree(u);
        if (x) cnt += prf[u] - prf[v];
        odd ^= x;
    }
    return odd;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;

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

    int originalLeaves = 0;
    for (int i = 1; i <= n; i++) {
        if ((int)adj[i].size() == 1) originalLeaves++;
        if ((int)adj[i].size() > 1) rt = i;
    }

    dfs(rt);
    memset(vis, 0, sizeof vis);
    calc(rt, 0);
    memset(vis, 0, sizeof vis);
    build();

    while (q--) {
        int t; cin >> t;
        vector<int> touched;
        cnt = t; // each added leaf-edge contributes 1

        for (int i = 0; i < t; i++) {
            int x; cin >> x;
            if (addcnt[x] == 0) touched.push_back(x);
            addcnt[x]++;
        }

        int leafCnt = originalLeaves + t;
        vector<pair<int, int>> nodes;

        for (int x : touched) {
            bool wasLeaf = ((int)adj[x].size() == 1);
            if (wasLeaf) leafCnt--; // the old original leaf x stops being a leaf once

            int deltaLeaves = addcnt[x] - (wasLeaf ? 1 : 0);
            if (deltaLeaves & 1) {
                markNode[x] = 1;
                nodes.push_back({in[x], x});
            }
        }

        if (leafCnt % 2) {
            cout << "-1\n";
            for (int x : touched) {
                addcnt[x] = 0;
                markNode[x] = 0;
            }
            continue;
        }

        if (!nodes.empty()) {
            sort(nodes.begin(), nodes.end());
            int sz = nodes.size();
            for (int i = 0; i + 1 < sz; i++) {
                int w = lca(nodes[i].second, nodes[i + 1].second);
                nodes.push_back({in[w], w});
            }
        }
        nodes.push_back({in[rt], rt});
        sort(nodes.begin(), nodes.end());
        nodes.erase(unique(nodes.begin(), nodes.end(), [](auto a, auto b) {
            return a.second == b.second;
        }), nodes.end());

        vector<int> st;
        st.push_back(rt);
        for (int i = 1; i < (int)nodes.size(); i++) {
            int x = nodes[i].second;
            while (!st.empty() && lca(st.back(), x) != st.back()) st.pop_back();
            vrt[st.back()].push_back(x);
            st.push_back(x);
        }

        solve_vtree(rt);
        cout << ans + cnt << '\n';

        for (auto [_, x] : nodes) vrt[x].clear();
        for (int x : touched) {
            addcnt[x] = 0;
            markNode[x] = 0;
        }
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…