#include <bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define ff first
#define ss second
#define bit(i) (1 << (i))
#define fto(i, a, b) for (int i = (a); i <= (b); ++i)
#define fdto(i, a, b) for (int i = (a); i >= (b); --i)
#define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i)
#define pb push_back
#define pf push_front
#define endl "\n"
#define oo (int)(998244353)
#define maxN 100005
#define l(s) s.length()
#define vi vector <int>
#define vii vector <ii>
#define fat(x, y) for (auto x : y)
#define fit(x, y) for (int x : y)
#define fiit(x, y) for (ii x : y)
#define EPS 1e-9
#define pi (acos(-1))
#define ll long long
int n, q, tme, root;
vi ke[maxN];
int sz[maxN], h[maxN], par[maxN], mark[maxN];
int top[maxN], pos[maxN];
int st[4*maxN], lazy[4*maxN];
int t[maxN];
void down(int id, int l, int r) {
lazy[id] = 0;
lazy[id*2] ^= 1;
lazy[id*2+1] ^= 1;
int m = (l+r)/2;
st[id*2] = (m-l+1) - st[id*2];
st[id*2+1] = (r-m) - st[id*2+1];
}
void ud(int id, int l, int r, int i, int j) {
if (l > j || r < i) return;
if (i <= l && r <= j) {
st[id] = (r-l+1) - st[id];
lazy[id] ^= 1;
return;
}
if (lazy[id]) down(id, l, r);
int m = (l+r)/2;
ud(id*2, l, m, i, j);
ud(id*2+1, m+1, r, i, j);
st[id] = st[id*2] + st[id*2+1];
}
void pre_dfs(int u) {
sz[u] = 1;
for (int v : ke[u]) if (v != par[u]) {
par[v] = u;
h[v] = h[u] + 1;
pre_dfs(v);
sz[u] += sz[v];
}
}
void hld(int u, int tp) {
top[u] = tp;
pos[u] = tme++;
int bigC = 0;
for (int v : ke[u]) if (v != par[u]) {
if (sz[v] > sz[bigC]) bigC = v;
}
//cout << u << " " << bigC << endl;
if (bigC) hld(bigC, tp);
for (int v : ke[u]) if (v != par[u]) {
if (v != bigC) hld(v, v);
}
}
void treeud(int u) {
while (1) {
ud(1, 1, n-1, pos[top[u]] + 1, pos[u]);
if (top[u] == root) break;
ud(1, 1, n-1, pos[top[u]], pos[top[u]]);
u = par[top[u]];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> q;
fto(i, 1, n-1) {
int u, v; cin >> u >> v;
ke[u].pb(v);
ke[v].pb(u);
}
fto(i, 1, n) if (ke[i].size() != 1) {
root = i;
break;
}
//cout << root << endl;
pre_dfs(root);
hld(root, root);
//return 0;
int cr = 0;
fto(i, 1, n) if (int(ke[i].size()) == 1) {
++cr;
treeud(i);
}
//cout << st[1] << endl;
while (q--) {
int d; cin >> d;
unordered_map<int, int> mp;
int cur = cr;
fto(i, 1, d) cin >> t[i];
fto(i, 1, d) {
cur++;
if (ke[t[i]].size() > 1 || mp.count(t[i])) treeud(t[i]);
else --cur;
mp[t[i]] = 1;
}
//cout << cur << endl;
if (cur%2 == 0) cout << 2*n - 2 - st[1] + d << endl;
else cout << -1 << endl;
mp.clear();
fto(i, 1, d) {
if (ke[t[i]].size() > 1 || mp.count(t[i])) treeud(t[i]);
mp[t[i]] = 1;
}
}
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... |