#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pib = pair<int, bool>;
const int MAX_N = 1e5 + 5, MAX_Q = 1e5 + 5;;
int n, q;
vector<int> adj[MAX_N];
vector<int> upd[MAX_Q];
int root;
vector<int> child[MAX_N];
bool is_1[MAX_N];
void dfs1(int u, int par) {
is_1[u] = (bool) (adj[u].size() == 1);
for (int v : adj[u]) {
if (v == par) continue;
child[u].push_back(v);
dfs1(v, u);
if (is_1[v]) is_1[u] = !is_1[u];
}
}
int n_1s[MAX_N], n_0s[MAX_N]; // From root to u
void dfs2(int u) {
n_1s[u] += is_1[u], n_0s[u] += !is_1[u];
for (int v : child[u]) {
n_1s[v] += n_1s[u], n_0s[v] += n_0s[u];
dfs2(v);
}
}
int tot_n_1s, tot_n_0s;
void precomp1() {
for (int i = 1; i <= n; i++) {
if (adj[i].size() == 1) continue;
root = i;
dfs1(root, -1);
break;
}
dfs2(root);
for (int i = 1; i <= n; i++)
tot_n_1s += is_1[i], tot_n_0s += !is_1[i];
// for (int i = 1; i <= n; i++) {
// cout << i << ": " << n_1s[i] << " " << n_0s[i] << endl;
// }
}
int new_child_size[MAX_N];
int n_leaves[MAX_Q];
int extra_n_1s[MAX_Q];
unordered_set<int> queries_w_flip1[MAX_N];
void precomp2(int query) {
for (int u : upd[query]) {
extra_n_1s[query]++;
if (new_child_size[u]) {
n_leaves[query]++;
if (queries_w_flip1[u].count(query)) queries_w_flip1[u].erase(query);
else queries_w_flip1[u].insert(query);
}
new_child_size[u]++;
}
for (int u : upd[query]) new_child_size[u]--;
// cout << query << ": " << n_leaves[query] << " " << extra_n_1s[query] << endl;
}
void init() {
for (int i = 1; i <= n; i++) new_child_size[i] = child[i].size();
int tot_n_leaves = 0;
for (int i = 1; i <= n; i++) tot_n_leaves += (bool) child[i].empty();
for (int i = 1; i <= q; i++) n_leaves[i] = tot_n_leaves;
}
unordered_map<int, int> queries_w_flip2[MAX_N]; // {query, prev flipped}
vector<pii> flip_path[MAX_Q]; // {high, low (not incl.)}
void dfs3(int u) {
unordered_map<int, bool> spec_queries; // {query, flip state}
for (int query : queries_w_flip1[u]) queries_w_flip2[u][query] = u;
for (int v : child[u]) {
dfs3(v);
if (queries_w_flip2[u].size() < queries_w_flip2[v].size()) queries_w_flip2[u].swap(queries_w_flip2[v]);
for (pii el : queries_w_flip2[v]) {
if (spec_queries.count(el.first)) {
flip_path[el.first].push_back({el.second, u});
spec_queries[el.first] = !spec_queries[el.first];
} else {
if (queries_w_flip2[u][el.first] == 0) queries_w_flip2[u][el.first] = el.second;
else {
spec_queries[el.first] = false;
flip_path[el.first].push_back({el.second, u}); flip_path[el.first].push_back({queries_w_flip2[u][el.first], u});
queries_w_flip2[u].erase(el.first);
}
}
}
}
for (pib el : spec_queries)
if (el.second) queries_w_flip2[u][el.first] = u;
}
void precomp3() {
dfs3(root);
for (pii el : queries_w_flip2[root])
flip_path[el.first].push_back({el.second, 0});
// for (int i = 1; i <= q; i++) {
// cout << i << ": ";
// for (pii el : flip_path[i]) cout << el.first << "," << el.second << " ";
// cout << endl;
// }
}
int check(int query) {
int ones = extra_n_1s[query], zeros = 1;
for (int u : upd[query])
new_child_size[u]++;
for (int u = 2; u <= n; u++)
ones += (bool) (new_child_size[u] % 2 == 1 || new_child_size[u] == 0), zeros += (bool) (new_child_size[u] % 2 == 0 && new_child_size[u] != 0);
for (int u : upd[query])
new_child_size[u]--;
return ones + 2 * (zeros - 1);
}
int main() {
// freopen("spring.in", "r", stdin);
cin >> n >> q; assert(n >= 3);
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= q; i++) {
int s; cin >> s;
for (int j = 1; j <= s; j++) {
int u; cin >> u;
upd[i].push_back(u);
}
}
precomp1();
init();
for (int i = 1; i <= q; i++) precomp2(i);
// for (int i = 1; i <= n; i++) {
// cout << i << " : ";
// for (int j : queries_w_flip1[i]) cout << j << " ";
// cout << endl;
// }
precomp3();
for (int query = 1; query <= q; query++) {
if (n_leaves[query] % 2 == 1) {
cout << "-1" << '\n';
continue;
}
int new_n_1s = tot_n_1s + extra_n_1s[query], new_n_0s = tot_n_0s;
for (pii path : flip_path[query]) {
int path_n_1s = n_1s[path.first] - n_1s[path.second], path_n_0s = n_0s[path.first] - n_0s[path.second];
new_n_1s += path_n_0s - path_n_1s, new_n_0s += path_n_1s - path_n_0s;
}
// int ans = new_n_1s + 2 * (new_n_0s - 1); assert(new_n_0s >= 1);
int ans = check(query);
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
22616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
23836 KB |
Output is correct |
| 2 |
Correct |
25 ms |
23772 KB |
Output is correct |
| 3 |
Correct |
59 ms |
27068 KB |
Output is correct |
| 4 |
Correct |
75 ms |
32008 KB |
Output is correct |
| 5 |
Correct |
95 ms |
32568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
25400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
80 ms |
30332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1038 ms |
47712 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1020 ms |
55772 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
22616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
