#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], sz[N];
vector<int> ch[N];
void dfs(int x) {
sz[x] = 1;
for (int y : ch[x]) {
ch[y].erase(find(ch[y].begin(), ch[y].end(), par[y] = x));
dfs(y);
sz[x] += sz[y];
}
}
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);
int leaf = 0, even = 0;
FOR(i, 1, n) {
if (sz[i] % 2 == 0) even++;
if (ch[i].size() + (i != 1) == 1) leaf++;
}
while (q--) {
int D;
cin >> D;
int new_leaf = leaf + D;
vector<int> a(D);
for (auto& x : a) {
cin >> x;
for (int y = x; y != 1; y = par[y]) {
even += sz[y] % 2 == 0 ? -1 : 1;
sz[y]++;
}
if (!seen[x]) {
seen[x] = 1;
if (ch[x].size() + (x != 1) == 1) new_leaf--;
}
}
cout << (new_leaf % 2 ? -1 : n - 1 + D + even) << "\n";
for (int x : a) {
for (int y = x; y != 1; y = par[y]) {
even += sz[y] % 2 == 0 ? -1 : 1;
sz[y]--;
}
seen[x] = 0;
}
}
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... |