#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
typedef long long ll;
int tree[1 << 18], tmp[1 << 18];
void push(int node, int s, int e){
if(!tmp[node]) return;
tree[node] = (e-s+1) - tree[node];
if(s != e){
tmp[node << 1] ^= 1;
tmp[node << 1 | 1] ^= 1;
}
tmp[node] = 0;
}
void update(int node, int s, int e, int l, int r){
push(node, s, e);
if(r < s || e < l) return;
if(l <= s && e <= r){ tmp[node] ^= 1; push(node, s, e); return; }
int m = s + e >> 1;
update(node << 1, s, m, l, r);
update(node << 1 | 1, m+1, e, l, r);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
int query(int node, int s, int e, int l, int r){
push(node, s, e);
if(r < s || e < l) return 0;
if(l <= s && e <= r) return tree[node];
int m = s + e >> 1;
return query(node << 1, s, m, l, r) + query(node << 1 | 1, m+1, e, l, r);
}
int n, q, leaf[101010];
vector<int> inp[101010], g[101010];
int top[101010], dep[101010], par[101010], sz[101010], in[101010], pv;
void dfs(int v, int b){
for(auto i : inp[v]) if(i != b) {
g[v].push_back(i);
dep[i] = dep[v] + 1; par[i] = v;
dfs(i, v);
}
}
void dfs1(int v){
sz[v] = 1;
for(auto &i : g[v]){
dfs1(i); sz[v] += sz[i];
if(sz[i] > sz[g[v][0]]) swap(i, g[v][0]);
}
}
int dfs2(int v){
in[v] = ++pv;
for(auto i : g[v]){
top[i] = i == g[v][0] ? top[v] : i;
dfs2(i);
}
}
void updatePath(int s, int e){
for(; top[s]!=top[e]; s=par[top[s]]){
if(dep[top[s]] < dep[top[e]]) swap(s, e);
update(1, 1, n, in[top[s]], in[s]);
}
if(dep[s] > dep[e]) swap(s, e);
update(1, 1, n, in[s], in[e]);
}
int getAns(int cnt){
if(query(1, 1, n, 1, 1)) return -1;
return 2*(n-1) - query(1, 1, n, 1, n) + cnt;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q;
for(int i=1; i<n; i++){
int s, e; cin >> s >> e;
inp[s].push_back(e); inp[e].push_back(s);
}
top[1] = 1; dfs(1, -1); dfs1(1); dfs2(1);
for(int i=1; i<=n; i++) if(inp[i].size() == 1) leaf[i] = 1, updatePath(1, i);
while(q--){
int cnt; cin >> cnt;
vector<int> add; set<int> st;
for(int i=0; i<cnt; i++){
int t; cin >> t;
if(!leaf[t] && !st.count(t)) add.push_back(t);
st.insert(t);
}
for(auto i : add) updatePath(1, i);
cout << getAns(cnt) << "\n";
for(auto i : add) updatePath(1, i);
}
}
Compilation message
cleaning.cpp: In function 'void update(int, int, int, int, int)':
cleaning.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | int m = s + e >> 1;
| ~~^~~
cleaning.cpp: In function 'int query(int, int, int, int, int)':
cleaning.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int m = s + e >> 1;
| ~~^~~
cleaning.cpp: In function 'int dfs2(int)':
cleaning.cpp:60:1: warning: no return statement in function returning non-void [-Wreturn-type]
60 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
10112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
10624 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
12032 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
14976 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
62 ms |
19068 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
93 ms |
24184 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
10112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
