5384 | 2023-04-29 10:35:01 | szil | Spring cleaning | cpp14 | Elfogadva 100/100 | 202ms | 71712 KiB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
struct Node {
int s = 0;
int left = 0;
int cnt = 0;
};
vector<int> g[MAXN];
int depth[MAXN], parent[MAXN], pos[MAXN], head[MAXN], heavy[MAXN], timer = 0, n, q, leaf[MAXN];
Node tree[2 * MAXN];
void build() {
for (int i = 2 * n; i > n; i--) {
tree[i].cnt = 1;
}
for (int i = n; i >= 1; i--) {
tree[i].cnt = tree[2*i].cnt + tree[2*i+1].cnt;
}
}
int dfs(int u, int d) {
depth[u] = d;
int s = 1, max_s = 0;
for (int v : g[u]) {
if (v != parent[u]) {
parent[v] = u;
int k = dfs(v, d + 1);
s += k;
if (k > max_s) {
max_s = k;
heavy[u] = v;
}
}
}
return s;
}
void decomp(int u, int h) {
head[u] = h;
pos[u] = ++timer;
if (heavy[u])
decomp(heavy[u], h);
for (int v : g[u]) {
if (v != parent[u] && v != heavy[u])
decomp(v, v);
}
}
void apply(int u) {
tree[u].s = tree[u].cnt - tree[u].s;
if (u <= n) tree[u].left ^= 1;
}
void build(int u) {
while (u > 1) {
u /= 2;
tree[u].s = tree[2*u].s + tree[2*u+1].s;
if (tree[u].left == 1)
tree[u].s = tree[u].cnt - tree[u].s;
}
}
int qry() {
return tree[1].cnt-tree[1].s;
}
void segupd(int l, int r) {
l += n; r += n;
int a = l, b = r;
while (l <= r) {
if (l % 2 == 1) apply(l++);
if (r % 2 == 0) apply(r--);
l /= 2; r /= 2;
}
build(a);
build(b);
}
void upd(int a, int b) {
for (; head[a] != head[b]; b = parent[head[b]]) {
if (depth[head[a]] > depth[head[b]])
swap(a, b);
segupd(pos[head[b]], pos[b]);
}
if (depth[a] > depth[b])
swap(a, b);
segupd(pos[a], pos[b]);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
for (int i = 0; i < n - 1; i++) {
int a, b; cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, 0);
decomp(1, 1);
build();
int leaves = 0;
for (int i = 1; i <= n; i++) {
leaf[i] = g[i].size() == 1;
if (leaf[i]) {
upd(1, i);
leaves++;
}
}
while (q--) {
int c; cin >> c;
vector<int> v(c);
for (int i = 0; i < c; i++) {
cin >> v[i];
if (leaf[v[i]] == 1) {
leaf[v[i]] = 2;
} else {
upd(1, v[i]);
leaves++;
}
}
if (leaves % 2 == 1) {
cout << "-1\n";
} else {
cout << n - 2 + c + qry() << "\n";
}
for (int i = 0; i < c; i++) {
if (leaf[v[i]] == 2) {
leaf[v[i]] = 1;
} else {
upd(1, v[i]);
leaves--;
}
}
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 4ms | 6632 KiB | ||||
2 | Elfogadva | 83ms | 11060 KiB | ||||
subtask2 | 9/9 | ||||||
3 | Elfogadva | 35ms | 9252 KiB | ||||
4 | Elfogadva | 34ms | 9848 KiB | ||||
5 | Elfogadva | 68ms | 25416 KiB | ||||
6 | Elfogadva | 71ms | 22756 KiB | ||||
7 | Elfogadva | 83ms | 28964 KiB | ||||
subtask3 | 9/9 | ||||||
8 | Elfogadva | 50ms | 15100 KiB | ||||
9 | Elfogadva | 50ms | 15548 KiB | ||||
10 | Elfogadva | 64ms | 45860 KiB | ||||
11 | Elfogadva | 128ms | 45540 KiB | ||||
12 | Elfogadva | 52ms | 46352 KiB | ||||
subtask4 | 16/16 | ||||||
13 | Elfogadva | 65ms | 23736 KiB | ||||
14 | Elfogadva | 39ms | 22592 KiB | ||||
15 | Elfogadva | 19ms | 23020 KiB | ||||
16 | Elfogadva | 17ms | 24360 KiB | ||||
17 | Elfogadva | 18ms | 25188 KiB | ||||
18 | Elfogadva | 48ms | 25436 KiB | ||||
subtask5 | 19/19 | ||||||
19 | Elfogadva | 149ms | 32884 KiB | ||||
20 | Elfogadva | 200ms | 34352 KiB | ||||
21 | Elfogadva | 143ms | 30492 KiB | ||||
22 | Elfogadva | 202ms | 37016 KiB | ||||
23 | Elfogadva | 200ms | 38308 KiB | ||||
subtask6 | 17/17 | ||||||
24 | Elfogadva | 196ms | 45932 KiB | ||||
25 | Elfogadva | 141ms | 53692 KiB | ||||
26 | Elfogadva | 157ms | 54284 KiB | ||||
27 | Elfogadva | 148ms | 59144 KiB | ||||
subtask7 | 30/30 | ||||||
28 | Elfogadva | 142ms | 47620 KiB | ||||
29 | Elfogadva | 146ms | 60784 KiB | ||||
30 | Elfogadva | 83ms | 57432 KiB | ||||
31 | Elfogadva | 122ms | 71712 KiB | ||||
32 | Elfogadva | 200ms | 54772 KiB | ||||
33 | Elfogadva | 140ms | 63628 KiB | ||||
34 | Elfogadva | 157ms | 69860 KiB | ||||
35 | Elfogadva | 158ms | 71476 KiB |