#include <bits/stdc++.h>
using namespace std;
long long m=1, k=1, p[100005], h[100005], st[400005], lazy[400005], dp[100005], tour[100005];
long long sz[100005], nxt[100005], head[100005], chain[100005], pos[100005], check[100005];
vector<long long> adj[100005], vv;
void dfs(long long x)
{
sz[x]=1;
for (auto y: adj[x])
{
if (y!=p[x])
{
h[y]=h[x]+1;
p[y]=x;
dfs(y);
sz[x]+=sz[y];
if (sz[y]>sz[nxt[x]]) {nxt[x]=y;};
dp[x]+=dp[y];
dp[x]%=2;
if (dp[x]==0) {dp[x]=2;};
};
};
if (x>1 && adj[x].size()==1) {dp[x]=1;};
}
void hld(long long x)
{
if (head[m]==0) {head[m]=x;};
chain[x]=m; tour[k]=x; pos[x]=k; k++;
if (nxt[x]>0) {hld(nxt[x]);};
for (auto y: adj[x])
{
if (y!=p[x] && y!=nxt[x])
{
m++;
hld(y);
};
};
}
void build(long long x, long long l, long long r)
{
if (l>r) {return;}
else if (l==r) {st[x]=dp[tour[l]];}
else
{
build(x*2, l, (l+r)/2);
build(x*2+1, (l+r)/2+1, r);
st[x]=st[x*2]+st[x*2+1];
};
}
void fix(long long x, long long l, long long r)
{
if (lazy[x]%2==1)
{
st[x]=3*(r-l+1)-st[x];
if (l<r) {lazy[x*2]+=lazy[x]; lazy[x*2+1]+=lazy[x];};
lazy[x]=0;
};
}
void update(long long x, long long l, long long r, long long pos1, long long pos2)
{
if (l<=r) {fix(x, l, r);};
if (l>r || l>pos2 || r<pos1) {return;}
else if (pos1<=l && r<=pos2) {lazy[x]++; fix(x, l, r);}
else
{
update(x*2, l, (l+r)/2, pos1, pos2);
update(x*2+1, (l+r)/2+1, r, pos1, pos2);
st[x]=st[x*2]+st[x*2+1];
};
}
long long get(long long x, long long l, long long r, long long pos1, long long pos2)
{
if (l>r || l>pos2 || r<pos1) {return 0LL;}
else if (pos1<=l && r<=pos2) {fix(x, l, r); return st[x];}
else {fix(x, l, r); return get(x*2, l, (l+r)/2, pos1, pos2)+get(x*2+1, (l+r)/2+1, r, pos1, pos2);};
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
long long n, q, i, u, v;
cin >> n >> q;
for (i=1; i<n; i++)
{
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
};
dfs(1);
hld(1);
build(1, 1, n);
while (q--)
{
cin >> i;
while (i--)
{
cin >> u;
vv.push_back(u);
check[u]++;
if (u>1 && adj[u].size()==1 && check[u]==1) {continue;};
while (u>0)
{
update(1, 1, n, pos[head[chain[u]]], pos[u]);
u=p[head[chain[u]]];
};
};
v=get(1, 1, n, pos[1], pos[1]);
if (adj[1].size()==1 && check[1]==0 && v==2) {cout << -1 << "\n";}
else if ((adj[1].size()>1 || check[1]) && v==1) {cout << -1 << "\n";}
else {cout << get(1, 1, n, 2, n)+vv.size() << "\n";};
while (!vv.empty())
{
u=vv.back();
vv.pop_back();
check[u]--;
if (u>1 && adj[u].size()==1 && check[u]==0) {continue;};
while (u>0)
{
update(1, 1, n, pos[head[chain[u]]], pos[u]);
u=p[head[chain[u]]];
};
};
};
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |