#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)size(x))
#define all(x) begin(x), end(x)
#define trace(x) cout << #x << ": " << (x) << endl;
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }
const int N = 200000, infI = 1e9 + 7;
const ll infL = 3e18;
vector<int> g[N];
int cnt[N], tin[N], rev[N], head[N], sz[N], parent[N], T = 0;
void dfs1(int v, int p) {
sz[v] = 1;
int mx = -1;
for (int i = 0; i < sz(g[v]); ++i) {
int to = g[v][i];
if (to != p) {
dfs1(to, v);
sz[v] += sz[to];
if (mx == -1 || sz[g[v][mx]] < sz[to]) {
mx = i;
}
}
}
if (mx != -1) {
swap(g[v][0], g[v][mx]);
}
}
void dfs2(int v, int p, int pp) {
if (pp == -1) {
head[v] = v;
} else {
head[v] = pp;
}
tin[v] = T++;
parent[v] = p;
rev[tin[v]] = v;
if (sz(g[v]) <= 1) {
cnt[v] = 1;
} else {
cnt[v] = 0;
dfs2(g[v][0], v, head[v]);
for (int i = 1; i < sz(g[v]); ++i) {
if (g[v][i] != p) {
dfs2(g[v][i], v, -1);
}
}
for (int to : g[v]) {
if (to != p) {
cnt[v] ^= cnt[to];
}
}
}
}
struct node {
int cnt[2] = {0, 0};
node() = default;
};
node operator+(node a, node b) {
return {a.cnt[0] + b.cnt[0], a.cnt[1] + b.cnt[1]};
}
vector<node> t;
vector<int> xored;
int siz = 1;
void init(int n) {
siz = 1;
while (siz < n) {
siz <<= 1;
}
t.assign(siz << 1, {});
xored.assign(siz << 1, 0);
for (int i = 0; i < n; ++i) {
++t[i + siz].cnt[cnt[rev[i]]];
}
for (int i = siz - 1; i > 0; --i) {
t[i] = t[i << 1] + t[i << 1 | 1];
}
}
void modify(int l, int r, int x = 1, int lx = 0, int rx = siz) {
if (l >= rx || lx >= r) {
return;
}
if (l <= lx && rx <= r) {
xored[x] ^= 1;
swap(t[x].cnt[0], t[x].cnt[1]);
return;
}
int m = (lx + rx) >> 1;
modify(l, r, x << 1, lx, m), modify(l, r, x << 1 | 1, m, rx);
t[x] = t[x << 1] + t[x << 1 | 1];
if (xored[x]) {
swap(t[x].cnt[0], t[x].cnt[1]);
}
}
void xor_path(int v) {
while (v != -1) {
modify(tin[head[v]], tin[v] + 1);
v = parent[head[v]];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
int root = -1;
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
--a, --b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 0; i < n; ++i) {
if (sz(g[i]) > 1) {
root = i;
break;
}
}
assert(root != -1);
dfs1(root, -1);
dfs2(root, -1, -1);
init(n);
int leaves = cnt[root];
while (q--) {
int D;
cin >> D;
vector<int> a(D);
for (int i = 0; i < D; ++i) {
cin >> a[i];
--a[i];
}
sort(all(a));
for (int i = 0; i < D; ++i) {
if (sz(g[a[i]]) > 1 || (i != 0 && a[i - 1] == a[i] || i != D - 1 && a[i + 1] == a[i])) {
xor_path(a[i]);
leaves ^= 1;
}
}
for (int i = 0; i < D; ++i) {
if (sz(g[a[i]]) == 1 && (i == D - 1 || a[i + 1] != a[i]))
leaves ^= 1;
}
if (leaves) {
cout << "-1\n";
} else {
cout << D + t[1].cnt[0] * 2 + t[1].cnt[1] * 1 - 2 << '\n';
}
for (int i = 0; i < D; ++i) {
if (sz(g[a[i]]) > 1 || ((i != 0 && a[i - 1] == a[i]) || (i != D - 1 && a[i + 1] == a[i]))) {
xor_path(a[i]);
leaves ^= 1;
}
}
for (int i = 0; i < D; ++i) {
if (sz(g[a[i]]) == 1 && (i == D - 1 || a[i + 1] != a[i]))
leaves ^= 1;
}
}
return 0;
}
Compilation message
cleaning.cpp: In function 'int main()':
cleaning.cpp:152:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
152 | if (sz(g[a[i]]) > 1 || (i != 0 && a[i - 1] == a[i] || i != D - 1 && a[i + 1] == a[i])) {
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
47 ms |
5972 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
6648 KB |
Output is correct |
2 |
Correct |
38 ms |
6648 KB |
Output is correct |
3 |
Correct |
48 ms |
22348 KB |
Output is correct |
4 |
Correct |
97 ms |
22008 KB |
Output is correct |
5 |
Correct |
51 ms |
21084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
80 ms |
8380 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
110 ms |
11588 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
186 ms |
15576 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |