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