#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj_list;
vector<int> nleafs;
vector<int> dp;
vector<int> dpl;
void dfs (int v, int p) {
dp[v] = 0;
dpl[v] = 0;
int cnt = 0;
for (auto &it : adj_list[v]) {
if (it == p) continue;
cnt++;
dfs(it, v);
dpl[v] += dpl[it];
dp[v] += 2 - (dpl[it] % 2);
dp[v] += dp[it];
}
if (cnt == 0 && nleafs[v] == 0) dpl[v]++;
if (cnt + nleafs[v] <= 1 && p == -1) dpl[v]++;
dpl[v] += nleafs[v];
dp[v] += nleafs[v];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
adj_list = vector<vector<int>> (n);
for (int i = 0; i < n-1; i++) {
int u, v;
cin >> u >> v;
adj_list[u-1].push_back(v-1);
adj_list[v-1].push_back(u-1);
}
vector<vector<int>> va (q);
for (int i = 0; i < q; i++) {
int d;
cin >> d;
for (int j = 0; j < d; j++) {
int a;
cin >> a;
va[i].push_back(a-1);
}
}
nleafs = vector<int> (n, 0);
dp = vector<int> (n, 0);
dpl = vector<int> (n, 0);
for (int i = 0; i < q; i++) {
for (auto &it: va[i]) {
nleafs[it]++;
}
dfs(0, -1);
if (dpl[0] % 2 == 1) dp[0] = -1;
cout << dp[0] << "\n";
for (auto &it: va[i]) {
nleafs[it]--;
}
}
return 0;
}
# | 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... |