#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
#define rep(i,n) for(int i = 0; i < n; i++)
vvi edges;
vi val;
vi parent, heavy, depth, head, pos;
struct SegTree{
vi Itree, lazy;
void init(int n){
while(n & (n - 1)) n++;
Itree.resize(2*n, 0);
lazy.resize(2*n, 0);
}
void update(int ind, int val){
ind += Itree.size() / 2;
Itree[ind] = val;
while(ind > 1){
ind /= 2;
Itree[ind] = Itree[ind * 2] + Itree[2 * ind + 1];
}
}
void lazyEval(int u, int a, int b){
if(lazy[u] == 1){
Itree[u] = (b - a) - Itree[u];
if(2*u < lazy.size()){
lazy[2*u] ^= 1;
lazy[2*u + 1] ^= 1;
}
lazy[u] = 0;
}
}
ll get2(ll u, ll l, ll r, ll a, ll b){
lazyEval(u, a, b);
if(l == a && r == b){
return Itree[u];
}
ll s = (a + b)/2;
if(r <= s){
return get2(2*u, l, r, a, s);
}else if(l >= s){
return get2(2*u + 1, l, r, s, b);
}else{
return get2(2*u, l, s, a, s) + get2(2*u + 1, s, r, s, b);
}
}
ll get(ll l, ll r){
return get2(1, l, r, 0, Itree.size() / 2);
}
void XORange2(ll u, ll l, ll r, ll a, ll b){
lazyEval(u, a, b);
if(l == a && r == b){
lazy[u] = 1;
lazyEval(u, a, b);
return;
}
ll s = (a + b)/2;
if(r <= s){
XORange2(2*u, l, r, a, s);
}else if(l >= s){
XORange2(2*u + 1, l, r, s, b);
}else{
XORange2(2*u, l, s, a, s);
XORange2(2*u + 1, s, r, s, b);
}
if(2*u < Itree.size()) {
lazyEval(2*u, a, s);
lazyEval(2*u + 1, s, b);
Itree[u] = Itree[2*u] + Itree[2*u + 1];
}
}
void XORange(ll l, ll r){
XORange2(1, l, r, 0, Itree.size() / 2);
}
};
ll listy = 0;
ll dfs(ll u){
ll max = -1;
ll ind = -1;
ll size = 1;
ll aktVal = 0;
rep(i, edges[u].size()){
ll v = edges[u][i];
if(parent[u] != v){
parent[v] = u;
depth[v] = depth[u] + 1;
ll x = dfs(v);
aktVal += val[v];
size += x;
if(x > max){
max = x;
ind = v;
}
}
}
if(ind == -1){
val[u] = 1;
listy++;
}else{
val[u] = (aktVal % 2);
}
heavy[u] = ind;
return size;
}
ll cur_pos;
void decompose(int u, int h){
head[u] = h;
pos[u] = cur_pos;
cur_pos++;
if(heavy[u] != -1){
decompose(heavy[u], h);
}
rep(i, edges[u].size()){
int v = edges[u][i];
if((parent[u] != v) && (v != heavy[u])){
decompose(v, v);
}
}
}
SegTree sg;
void initSegTree(){
ll n = edges.size();
sg.init(n);
rep(i, n){
sg.update(pos[i], val[i]);
}
}
void initHLD(){
int n = edges.size();
parent.resize(n, -1);
heavy.resize(n, -1);
depth.resize(n, 0);
pos.resize(n, -1);
head.resize(n, -1);
cur_pos = 0;
dfs(0);
decompose(0, 0);
initSegTree();
}
ll query(int u, int v){
ll ans = 0;
for(; head[u] != head[v]; v = parent[head[v]]){
if(depth[head[u]] > depth[head[v]]){
swap(u, v);
}
ans = max(ans, sg.get(pos[head[v]], pos[v] + 1));
}
ans = max(ans, sg.get(min(pos[v], pos[u]), max(pos[v], pos[u]) + 1));
return ans;
}
void queryUPD(int u, int v){
for(; head[u] != head[v]; v = parent[head[v]]){
if(depth[head[u]] > depth[head[v]]){
swap(u, v);
}
sg.XORange(pos[head[v]], pos[v] + 1);
}
sg.XORange(min(pos[v], pos[u]), max(pos[v], pos[u]) + 1);
}
int main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n, q;
cin >> n >> q;
edges.resize(n);
val.resize(n, 0);
//rep(i, n) cin >> val[i];
rep(i, n-1){
int a, b;
cin >> a >> b;
a--; b--;
edges[a].push_back(b);
edges[b].push_back(a);
}
initHLD();
vi was(n, 0);
if(edges[0].size() == 1) listy++;
rep(i, q){
int d;
cin >> d;
vi add(d);
vi upd;
rep(j, d){
cin >> add[j];
add[j]--;
if(!((edges[add[j]].size() == 1) && (was[add[j]] == 0))) {
queryUPD(0, add[j]);
upd.push_back(add[j]);
was[upd[j]] = 1;
}
}
ll ans = sg.get(1, n);
rep(j, upd.size()){
queryUPD(0, upd[j]);
was[upd[j]] = 0;
}
if((listy + upd.size()) % 2 == 0) cout << 2*(n - 1) - ans + d << endl;
else cout << -1 << endl;
}
}
Compilation message
cleaning.cpp: In member function 'void SegTree::lazyEval(int, int, int)':
cleaning.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | if(2*u < lazy.size()){
| ~~~~^~~~~~~~~~~~~
cleaning.cpp: In member function 'void SegTree::XORange2(long long int, long long int, long long int, long long int, long long int)':
cleaning.cpp:81:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | if(2*u < Itree.size()) {
| ~~~~^~~~~~~~~~~~~~
cleaning.cpp: In function 'long long int dfs(long long int)':
cleaning.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define rep(i,n) for(int i = 0; i < n; i++)
......
101 | rep(i, edges[u].size()){
| ~~~~~~~~~~~~~~~~~~
cleaning.cpp:101:5: note: in expansion of macro 'rep'
101 | rep(i, edges[u].size()){
| ^~~
cleaning.cpp: In function 'void decompose(int, int)':
cleaning.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define rep(i,n) for(int i = 0; i < n; i++)
......
134 | rep(i, edges[u].size()){
| ~~~~~~~~~~~~~~~~~~
cleaning.cpp:134:5: note: in expansion of macro 'rep'
134 | rep(i, edges[u].size()){
| ^~~
cleaning.cpp: In function 'int main()':
cleaning.cpp:9:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | #define rep(i,n) for(int i = 0; i < n; i++)
......
225 | rep(j, upd.size()){
| ~~~~~~~~~~~~~
cleaning.cpp:225:9: note: in expansion of macro 'rep'
225 | rep(j, upd.size()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
11 ms |
7772 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
3796 KB |
Output is correct |
| 2 |
Correct |
37 ms |
3784 KB |
Output is correct |
| 3 |
Correct |
47 ms |
25860 KB |
Output is correct |
| 4 |
Correct |
110 ms |
26084 KB |
Output is correct |
| 5 |
Correct |
40 ms |
23884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
9820 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
195 ms |
11860 KB |
Output is correct |
| 2 |
Runtime error |
32 ms |
21840 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
274 ms |
18352 KB |
Output is correct |
| 2 |
Correct |
196 ms |
22276 KB |
Output is correct |
| 3 |
Correct |
237 ms |
20712 KB |
Output is correct |
| 4 |
Correct |
229 ms |
22096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
11 ms |
7772 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
