#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 1e5 + 69;
const int K = 17;
pair<int, int> st[4 * N];
int n, q, ch[N], par[N], leaf[N], is[N], dep[N];
int tin[N], timer, top[N], sz[N];
vector<int> g[N];
void dfs(int v, int p) {
par[v] = p;
sz[v] = 1;
if (g[v].size() == 1)
leaf[v] = ch[v] = is[v] = 1;
for (auto u : g[v]) {
if (u == p)
continue;
dep[u] = dep[v] + 1;
dfs(u, v);
ch[v] += ch[u];
sz[v] += sz[u];
}
}
void modify(int v, int tl, int tr, int p, int x) {
if (tl == tr) {
if (x % 2 == 0)
st[v] = {0, 1};
else
st[v] = {1, 0};
}
else {
int mid = (tl + tr) / 2;
if (p <= mid)
modify(v * 2, tl, mid, p, x);
else
modify(v * 2 + 1, mid + 1, tr, p, x);
st[v] = {st[v * 2].f + st[v * 2 + 1].f, st[v * 2].s + st[v * 2 + 1].s};
}
}
void svapuj(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return;
else if (tl >= l && tr <= r)
st[v] = {st[v].s, st[v].f};
else {
int mid = (tl + tr) / 2;
svapuj(v * 2, tl, mid, l, r);
svapuj(v * 2 + 1, mid + 1, tr, l, r);
st[v] = {st[v * 2].f + st[v * 2 + 1].f, st[v * 2].s + st[v * 2 + 1].s};
}
}
pair<int, int> get(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return {0, 0};
else if (tl >= l && tr <= r)
return st[v];
else {
int mid = (tl + tr) / 2;
auto ll = get(v * 2, tl, mid, l, r);
auto rr = get(v * 2 + 1, mid + 1, tr, l, r);
pair<int, int> res;
res.f = {ll.f + rr.f};
res.s = {ll.s + rr.s};
return res;
}
}
void hld(int v, int p, int tp) {
int s = -1;
tin[v] = ++timer;
top[v] = tp;
modify(1, 1, n, tin[v], ch[v]);
for (auto u : g[v]) {
if (u == p)
continue;
if (s == -1 || sz[s] < sz[u])
s = u;
}
if (s != -1)
hld(s, v, tp);
for (auto u : g[v]) {
if (u == p || u == s)
continue;
hld(u, v, u);
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (int i = 1;i <= n - 1;i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, 0);
hld(1, 0, 1);
int uk = ch[1];
while (q--) {
int t;
cin >> t;
int a[t];
for (int i = 0;i < t;i++) {
cin >> a[i];
int v = a[i];
uk++;
if (leaf[v]) {
leaf[v]--;
uk--;
int v = a[i];
while (v > 0) {
svapuj(1, 1, n, tin[top[v]], tin[v]);
v = par[top[v]];
}
}
v = a[i];
while (v > 0) {
svapuj(1, 1, n, tin[top[v]], tin[v]);
v = par[top[v]];
}
}
if (uk % 2 == 1)
cout << "-1\n";
else {
pair<int, int> res;
res = get(1, 1, n, 2, n);
cout << res.f + 2 * res.s + t << '\n';
}
for (int i = 0;i < t;i++) {
uk--;
int v = a[i];
if (is[a[i]] && !leaf[a[i]]) {
uk++;
leaf[a[i]] = 1;
while (v > 0) {
svapuj(1, 1, n, tin[top[v]], tin[v]);
v = par[top[v]];
}
}
v = a[i];
while (v > 0) {
svapuj(1, 1, n, tin[top[v]], tin[v]);
v = par[top[v]];
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
177 ms |
8032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
8752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
224 ms |
12064 KB |
Output is correct |
| 2 |
Incorrect |
360 ms |
11932 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
298 ms |
13904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 2 |
Incorrect |
177 ms |
8032 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
