Submission #1228189

#TimeUsernameProblemLanguageResultExecution timeMemory
1228189TurkhuuSpring cleaning (CEOI20_cleaning)C++20
28 / 100
1096 ms14416 KiB
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i = (a); i <= (b); i++)
#define ROF(i, a, b) for (auto i = (a); i >= (b); i--)
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
bool seen[N];
int par[N], zleaf[N], even = 0;
vector<int> ch[N];
void dfs(int x) {
    if ((int)ch[x].size() + (x != 1) == 1) zleaf[x] = 1;
    for (int y : ch[x]) {
        ch[y].erase(find(ch[y].begin(), ch[y].end(), par[y] = x));
        dfs(y);
        zleaf[x] ^= zleaf[y];
    }
    if (zleaf[x] % 2 == 0) even++;
}
void flip(int x) {
    for (int y = x; y; y = par[y]) {
        even += zleaf[y] % 2 == 0 ? -1 : 1;
        zleaf[y] ^= 1;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    FOR(i, 1, n - 1) {
        int a, b;
        cin >> a >> b;
        ch[a].push_back(b);
        ch[b].push_back(a);
    }
    dfs(1);
    while (q--) {
        int D;
        cin >> D;
        int Zleaf = zleaf[1] ^ D;
        vector<int> a(D);
        for (auto& x : a) {
            cin >> x;
            flip(x);
            if (!seen[x] && ch[x].size() + (x != 1) == 1)
                flip(x), seen[x] = 1, Zleaf ^= 1;
        }
        cout << (Zleaf % 2 ? -1 : n - 1 + D + even - 1) << "\n";
        for (int x : a) {
            flip(x);
            if (seen[x] && ch[x].size() + (x != 1) == 1)
                flip(x), seen[x] = 0, Zleaf ^= 1;
        }
    }
    return 6/22;
}
#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...