#include<bits/stdc++.h>
using namespace std;
struct ainthelp{
int nr1, nr2;
bool swp;
};
const int N = 1e5 + 5;
vector<int> gr[N];
int sum[N];
int aux[N];
bool isleaf[N];
int sz[N];
int id[N];
int head[N];
int par[N];
ainthelp aint[4*N];
int n, nrleaf;
void propag(int nod, int l, int r){
if(aint[nod].swp){
aint[nod].swp = false;
swap(aint[nod].nr1, aint[nod].nr2);
if(l != r){
aint[2*nod].swp ^=true;
aint[2*nod + 1].swp ^= true;
}
}
}
void build(int nod, int l, int r){
if(l == r){
if(aux[l] == 0)
return;
if(aux[l] %2 == 0)
aint[nod].nr2 = 1;
else
aint[nod].nr1 = 1;
return;
}
int mid = (l + r)/2;
build(2*nod, l, mid);
build(2*nod + 1, mid + 1, r);
aint[nod] = {aint[2*nod].nr1 + aint[2*nod + 1].nr1, aint[2*nod].nr2 + aint[2*nod + 1].nr2, false};
}
void update(int nod, int l, int r, int ul, int ur){
propag(nod, l, r);
if(l > ur || r < ul)
return;
if(ul <= l && r <= ur){
aint[nod].swp ^= true;
propag(nod, l, r);
return;
}
int mid = (l + r)/2;
update(2*nod, l, mid, ul, ur);
update(2*nod + 1, mid + 1, r, ul, ur);
aint[nod] = {aint[2*nod].nr1 + aint[2*nod + 1].nr1, aint[2*nod].nr2 + aint[2*nod + 1].nr2, false};
}
void buildsum(int nod, int dad){
bool ok = false;
sz[nod] = 1;
for(auto x:gr[nod]){
if(x != dad){
buildsum(x, nod);
ok = true;
sum[nod] += sum[x];
sz[nod] += sz[x];
}
}
if(ok == false){
sum[nod] = 1;
isleaf[nod] = true;
nrleaf++;
}
if(dad == 0)
sum[nod] = 0;
}
void build_hld(int nod, int dad, int hd, int &cnt){
id[nod] = ++cnt;
aux[cnt] = sum[nod];
head[nod] = hd;
par[nod] = dad;
int vmson = 0, mson = -1;
for(auto x:gr[nod]){
if(x == dad)
continue;
if(sz[x] > vmson){
vmson = sz[x];
mson = x;
}
}
if(mson == -1)
return;
build_hld(mson, nod, hd, cnt);
for(auto x:gr[nod]){
if(x == dad || x == mson)
continue;
build_hld(x, nod, x, cnt);
}
}
int addlf[N];
void update_hld(int nod){
while(nod != 0){
int othnod = head[nod];
update(1, 1, n, id[othnod], id[nod]);
nod = par[othnod];
}
}
int main()
{
//freopen(".in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int q;
cin>>n>>q;
for(int i = 1; i < n; i++){
int a, b;
cin>>a>>b;
gr[a].push_back(b);
gr[b].push_back(a);
}
int root = 1;
while(gr[root].size() == 1)
root++;
buildsum(root, 0);
int cnt = 0;
build_hld(root, 0, root, cnt);
build(1, 1, n);
for(int i = 1; i <=q; i++){
vector<int> nl;
int d;
cin>>d;
for(int j = 1; j <=d; j++){
int x;
cin>>x;
nl.push_back(x);
}
for(auto x:nl){
if(isleaf[x] == true && addlf[x] == 0){
addlf[x]++;
continue;
}
nrleaf++;
update_hld(x);
addlf[x]++;
}
propag(1, 1, n);
int ans = aint[1].nr1 + 2 * aint[1].nr2;
if(nrleaf%2 == 0)
cout<<ans + d<<"\n";
else
cout<<"-1\n";
for(auto x:nl){
if(isleaf[x] == true && addlf[x] == 1){
addlf[x]--;
continue;
}
nrleaf--;
update_hld(x);
addlf[x]--;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
522 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
522 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
