#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |