This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct SegmentTree {
int n;
vector<int> t;
SegmentTree(int n) : n(n), t(2 * n) {}
int get(int l, int r) {
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1)
res ^= t[l++];
if (r & 1)
res ^= t[--r];
}
return res;
}
void update(int x) {
for (x += n; x > 0; x >>= 1) {
t[x] ^= 1;
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<vector<int>> e(n);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
e[u].push_back(v);
e[v].push_back(u);
}
vector<int> c(n), in(n), out(n);
vector s(2, vector<int>(n));
int timeStamp = 0;
int cnt = 0;
function<void(int, int)> dfs = [&](int u, int p) {
in[u] = timeStamp++;
c[u] = e[u].size() <= 1;
cnt += c[u];
for (int v : e[u]) {
if (v != p) {
dfs(v, u);
c[u] ^= c[v];
}
}
out[u] = timeStamp;
};
dfs(0, -1);
int f[2] {};
dfs = [&](int u, int p) {
if (p != -1) {
s[1][u] += c[u];
s[0][u] += !c[u];
f[c[u]]++;
}
for (int v : e[u]) {
if (v != p) {
s[1][v] = s[1][u];
s[0][v] = s[0][u];
dfs(v, u);
}
}
};
dfs(0, -1);
SegmentTree t(n);
while (q--) {
int k;
cin >> k;
vector<int> d(k);
for (int i = 0; i < k; i++) {
cin >> d[i];
d[i]--;
}
set<int> v(d.begin(), d.end());
int leaves = cnt + k;
for (int x : v) {
if (e[x].size() <= 1) {
leaves--;
}
}
if (leaves % 2 != 0) {
cout << "-1\n";
continue;
}
int a[2] {f[0], f[1]};
set<int> done;
sort(d.begin(), d.end(), [&](int i, int j) {
return in[i] > in[j];
});
for (int u : d) {
if (e[u].size() <= 1 && !done.count(u)) {
// nothing?
} else {
int x = t.get(in[u], out[u]);
a[1] -= s[1 ^ x][u];
a[1] += s[0 ^ x][u];
a[0] -= s[0 ^ x][u];
a[0] += s[1 ^ x][u];
t.update(in[u]);
}
done.insert(u);
}
int ans = 2 * a[0] + a[1] + k;
cout << ans << "\n";
done.clear();
for (int u : d) {
if (e[u].size() <= 1 && !done.count(u)) {
// nothing?
} else {
int x = t.get(in[u], out[u]);
t.update(in[u]);
}
done.insert(u);
}
}
return 0;
}
Compilation message (stderr)
cleaning.cpp: In function 'int main()':
cleaning.cpp:137:21: warning: unused variable 'x' [-Wunused-variable]
137 | int x = t.get(in[u], out[u]);
| ^
# | 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... |