#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int n, q, kor=0, brl=0, ans=0, par[300005];
vector<int> gr[300005];
bool used[300005];
int lst[300005], gol[300005];
void dfs(int v)
{
gol[v]=1;
used[v]=1;
int brs=gr[v].size();
if(brs==1) {brl++; lst[v]=1;}
for(int i=0; i<brs; i++)
{
int nv=gr[v][i];
if(used[nv]) continue;
par[nv]=v;
dfs(nv);
lst[v]+=lst[nv];
gol[v]+=gol[nv];
}
if(v!=kor && !(lst[v]&1)) ans++;
}
int nvt[300005];
int brchains=1, tv=0;
int chain[300005][2];
int to_chain[300005];
int red[300005], pos[300005];
int stojnost[300005];
void create_hld(int v)
{
tv++;
red[tv]=v;
pos[v]=tv;
to_chain[v]=brchains;
int brs=gr[v].size();
if(!brs) return;
create_hld(gr[v][0]);
for(int i=1; i<brs; i++)
{
chain[brchains][1]=tv;
chain[brchains+1][0]=tv+1;
brchains++;
create_hld(gr[v][i]);
}
}
bool promlst[300005];
bool osob[300005];
int tree[2000005];
int lazy[2000005];
void push_lazy(int v, int le, int ri)
{
if(!lazy[v]) return;
tree[v]=(ri-le+1)-tree[v];
if(le!=ri) {lazy[2*v]^=1; lazy[2*v+1]^=1;}
lazy[v]=0;
}
void update(int v, int le, int ri, int be, int en)
{
push_lazy(v, le, ri);
if(le>en || ri<be) return;
if(be<=le && ri<=en)
{
lazy[v]^=1;
push_lazy(v, le, ri);
return;
}
int mid=(le+ri)/2;
update(2*v, le, mid, be, en);
update(2*v+1, mid+1, ri, be, en);
tree[v]=tree[2*v]+tree[2*v+1];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=0; i<n-1; i++)
{
int a, b;
cin>>a>>b;
gr[a].push_back(b);
gr[b].push_back(a);
}
for(int i=1; i<=n; i++) if(gr[i].size()>1 && !kor) kor=i;
dfs(kor);
for(int i=1; i<=n; i++)
{
int brs=gr[i].size();
if(i==kor) brs++;
for(int j=0; j<brs-1; j++)
{
int nv=gr[i][j];
if(par[i]==nv) swap(gr[i][j], gr[i][brs-1]);
else if(gol[nv]>gol[gr[i][0]]) swap(gr[i][j], gr[i][0]);
}
gr[i].resize(brs-1);
}
/**
for(int i=1; i<=n; i++)
{
cout<<"Vryh "<<i<<": {";
for(int j=0; j<gr[i].size(); j++) cout<<gr[i][j]<<" ";
cout<<"}\n";
}*/
chain[1][0]=1;
create_hld(kor);
chain[brchains][1]=n;
/**
for(int i=1; i<=n; i++) cout<<red[i]<<" ";
cout<<endl<<brchains<<endl;
for(int i=1; i<=brchains; i++) cout<<chain[i][0]<<" "<<chain[i][1]<<endl;
for(int i=1; i<=n; i++) cout<<pos[i]<<" ";
cout<<endl;
for(int i=1; i<=n; i++) cout<<to_chain[i]<<" ";
cout<<endl;*/
for(int i=1; i<=n; i++)
{
if(i!=kor && !(lst[i]&1)) {update(1, 1, n, pos[i], pos[i]);}
}
for(int i=0; i<q; i++)
{
int d, brl=lst[kor];
cin>>d;
brl+=d;
for(int i=0; i<d; i++)
{
cin>>nvt[i];
if(nvt[i]==kor) continue;
if(!promlst[nvt[i]] && !gr[nvt[i]].size())
{
brl--;
promlst[nvt[i]]=1;
osob[i]=1;
continue;
}
int tekchain=to_chain[nvt[i]], tpos=pos[nvt[i]], tv=nvt[i];
while(tekchain!=1)
{
int lpos=chain[tekchain][0];
/// cout<<lpos<<" "<<tpos<<endl;
update(1, 1, n, lpos, tpos);
tv=par[red[lpos]];
tpos=pos[tv];
tekchain=to_chain[tv];
}
if(tpos>1) update(1, 1, n, 2, tpos);
}
if(brl&1) cout<<-1<<endl;
else cout<<n-1+d+tree[1]<<endl;
for(int i=0; i<d; i++)
{
promlst[nvt[i]]=0;
if(nvt[i]==kor || osob[i])
{
osob[i]=0;
continue;
}
osob[i]=0;
int tekchain=to_chain[nvt[i]], tpos=pos[nvt[i]], tv=nvt[i];
while(tekchain!=1)
{
int lpos=chain[tekchain][0];
update(1, 1, n, lpos, tpos);
tv=par[red[lpos]];
tpos=pos[tv];
tekchain=to_chain[tv];
}
if(tpos>1) update(1, 1, n, 2, tpos);
}
}
return 0;
}
/*
12 3
1 3
4 1
9 1
8 3
3 7
10 2
11 2
2 6
4 5
4 6
9 12
3 1 4 7
2 5 8
1 12
7 4
1 2
2 4
4 5
5 6
5 7
3 4
1 7
1 4
2 2 4
1 1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 2 |
Correct |
101 ms |
20628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
19288 KB |
Output is correct |
| 2 |
Correct |
32 ms |
19512 KB |
Output is correct |
| 3 |
Correct |
22 ms |
24272 KB |
Output is correct |
| 4 |
Correct |
43 ms |
24272 KB |
Output is correct |
| 5 |
Correct |
44 ms |
25544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
20052 KB |
Output is correct |
| 2 |
Correct |
63 ms |
20032 KB |
Output is correct |
| 3 |
Correct |
38 ms |
32856 KB |
Output is correct |
| 4 |
Correct |
135 ms |
32600 KB |
Output is correct |
| 5 |
Correct |
33 ms |
30928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1065 ms |
21008 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
25424 KB |
Output is correct |
| 2 |
Correct |
180 ms |
23380 KB |
Output is correct |
| 3 |
Correct |
155 ms |
21332 KB |
Output is correct |
| 4 |
Correct |
181 ms |
23292 KB |
Output is correct |
| 5 |
Correct |
182 ms |
23396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
27984 KB |
Output is correct |
| 2 |
Execution timed out |
1058 ms |
29020 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
18780 KB |
Output is correct |
| 2 |
Correct |
101 ms |
20628 KB |
Output is correct |
| 3 |
Correct |
32 ms |
19288 KB |
Output is correct |
| 4 |
Correct |
32 ms |
19512 KB |
Output is correct |
| 5 |
Correct |
22 ms |
24272 KB |
Output is correct |
| 6 |
Correct |
43 ms |
24272 KB |
Output is correct |
| 7 |
Correct |
44 ms |
25544 KB |
Output is correct |
| 8 |
Correct |
60 ms |
20052 KB |
Output is correct |
| 9 |
Correct |
63 ms |
20032 KB |
Output is correct |
| 10 |
Correct |
38 ms |
32856 KB |
Output is correct |
| 11 |
Correct |
135 ms |
32600 KB |
Output is correct |
| 12 |
Correct |
33 ms |
30928 KB |
Output is correct |
| 13 |
Execution timed out |
1065 ms |
21008 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
