53842023-04-29 10:35:01szilSpring cleaningcpp14Accepted 100/100202ms71712 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--;
    			}
    		}
     
    	}
    }
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms6632 KiB
2Accepted83ms11060 KiB
subtask29/9
3Accepted35ms9252 KiB
4Accepted34ms9848 KiB
5Accepted68ms25416 KiB
6Accepted71ms22756 KiB
7Accepted83ms28964 KiB
subtask39/9
8Accepted50ms15100 KiB
9Accepted50ms15548 KiB
10Accepted64ms45860 KiB
11Accepted128ms45540 KiB
12Accepted52ms46352 KiB
subtask416/16
13Accepted65ms23736 KiB
14Accepted39ms22592 KiB
15Accepted19ms23020 KiB
16Accepted17ms24360 KiB
17Accepted18ms25188 KiB
18Accepted48ms25436 KiB
subtask519/19
19Accepted149ms32884 KiB
20Accepted200ms34352 KiB
21Accepted143ms30492 KiB
22Accepted202ms37016 KiB
23Accepted200ms38308 KiB
subtask617/17
24Accepted196ms45932 KiB
25Accepted141ms53692 KiB
26Accepted157ms54284 KiB
27Accepted148ms59144 KiB
subtask730/30
28Accepted142ms47620 KiB
29Accepted146ms60784 KiB
30Accepted83ms57432 KiB
31Accepted122ms71712 KiB
32Accepted200ms54772 KiB
33Accepted140ms63628 KiB
34Accepted157ms69860 KiB
35Accepted158ms71476 KiB