/**
* author: wxhtzdy
* created: 01.07.2022 19:07:12
**/
#include <bits/stdc++.h>
using namespace std;
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
const int MAX = 200000;
vector<vector<int>> g(MAX);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
--u; --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> cnt(n);
int ans = 0;
const int L = 20;
vector<vector<int>> jump(n, vector<int>(L));
vector<int> dep(n);
vector<int> tin(n);
int T = 0;
function<void(int, int)> Dfs = [&](int v, int pr) {
tin[v] = ++T;
dep[v] = dep[pr] + 1;
jump[v][0] = pr;
if ((int) g[v].size() <= 1) {
cnt[v] += 1;
}
for (int u : g[v]) {
if (u != pr) {
Dfs(u, v);
cnt[v] += cnt[u];
}
}
if (pr != v) {
ans += 2 - (cnt[v] % 2);
}
};
int root;
for (int i = 0; i < n; i++) {
if ((int) g[i].size() > 1) {
root = i;
}
}
Dfs(root, root);
for (int j = 1; j < L; j++) {
for (int i = 0; i < n; i++) {
jump[i][j] = jump[jump[i][j - 1]][j - 1];
}
}
auto LCA = [&](int v, int u) {
if (dep[u] > dep[v]) {
swap(u, v);
}
for (int i = L - 1; i >= 0; i--) {
if (dep[jump[v][i]] >= dep[u]) {
v = jump[v][i];
}
}
for (int i = L - 1; i >= 0; i--) {
if (jump[u][i] != jump[v][i]) {
u = jump[u][i];
v = jump[v][i];
}
}
return u == v ? v : jump[v][0];
};
vector<vector<int>> cc(n, vector<int>(2));
Dfs = [&](int v, int pr) {
cc[v] = cc[pr];
cc[v][cnt[v] % 2] += 1;
for (int u : g[v]) {
if (u != pr) {
Dfs(u, v);
}
}
};
Dfs(root, root);
int tot = 0;
for (int i = 0; i < n; i++) {
if ((int) g[i].size() <= 1) {
tot += 1;
}
}
vector<int> par(MAX);
vector<int> sub(MAX);
while (q--) {
int d;
cin >> d;
vector<int> a(d);
for (int i = 0; i < d; i++) {
cin >> a[i];
--a[i];
}
sort(a.begin(), a.end(), [&](int i, int j) {
return tin[i] < tin[j];
});
int ntot = tot + d;
for (int i = 0; i < d; i++) {
if (i == 0 || a[i] != a[i - 1]) {
if ((int) g[a[i]].size() == 1) {
ntot -= 1;
sub[a[i]] -= 1;
}
}
}
vector<int> xs(1, root);
for (int i = 0; i < d; i++) {
xs.push_back(a[i]);
if (i > 0) {
xs.push_back(LCA(a[i], a[i - 1]));
}
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
sort(xs.begin(), xs.end(), [&](int i, int j) {
return tin[i] < tin[j];
});
vector<int> stk(1, root);
for (int i = 0; i < (int) xs.size(); i++) {
while (!stk.empty() && LCA(stk.back(), xs[i]) != stk.back()) {
stk.pop_back();
}
par[xs[i]] = stk.back();
stk.push_back(xs[i]);
}
for (int i = 0; i < d; i++) {
sub[a[i]] += 1;
}
for (int i = (int) xs.size() - 1; i >= 0; i--) {
if (xs[i] != 0) {
sub[par[xs[i]]] += sub[xs[i]];
}
}
int nans = ans + d;
for (int i = 0; i < (int) xs.size(); i++) {
if (sub[xs[i]] % 2 == 1) {
int c0 = cc[xs[i]][0] - cc[par[xs[i]]][0];
int c1 = cc[xs[i]][1] - cc[par[xs[i]]][1];
nans -= c0;
nans += c1;
}
}
if (ntot % 2 == 0) {
cout << nans << '\n';
} else {
cout << -1 << '\n';
}
for (int i : xs) {
sub[i] = 0;
}
}
return 0;
}
Compilation message
cleaning.cpp: In function 'int main()':
cleaning.cpp:113:31: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
113 | return u == v ? v : jump[v][0];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6484 KB |
Output is correct |
| 2 |
Incorrect |
105 ms |
11140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
8624 KB |
Output is correct |
| 2 |
Correct |
37 ms |
8592 KB |
Output is correct |
| 3 |
Correct |
78 ms |
28620 KB |
Output is correct |
| 4 |
Correct |
114 ms |
23348 KB |
Output is correct |
| 5 |
Correct |
169 ms |
30020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
9668 KB |
Output is correct |
| 2 |
Correct |
29 ms |
9688 KB |
Output is correct |
| 3 |
Correct |
85 ms |
38672 KB |
Output is correct |
| 4 |
Correct |
116 ms |
37308 KB |
Output is correct |
| 5 |
Correct |
77 ms |
35788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
11696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
21168 KB |
Output is correct |
| 2 |
Incorrect |
192 ms |
22128 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
232 ms |
29308 KB |
Output is correct |
| 2 |
Correct |
218 ms |
34552 KB |
Output is correct |
| 3 |
Correct |
259 ms |
33612 KB |
Output is correct |
| 4 |
Correct |
229 ms |
34536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6484 KB |
Output is correct |
| 2 |
Incorrect |
105 ms |
11140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
