#include<bits/stdc++.h> #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " #pragma GCC optimize("Ofast") #define int long long using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int range_rng(int l, int r) { return uniform_int_distribution<int>(l,r)(rng); } vector<int> nodes[200005]; int h[200005]; int u[200005]; int p[200005]; bool is_leaf[200005]; int leaves[200005]; int sz[200005]; int heavychild[200005]; int pathend[200005]; int stamp[200005]; int revstamp[200005]; int timer,root,ans,n; bool ok; struct Node { int maxval; int lazy; }; class AINT { public: Node aint[800005]; vector<int> trims; Node combine(Node a, Node b) { Node c; c.lazy=0; c.maxval=max(a.maxval,b.maxval); ///lazy e mereu 0 return c; } void prop(int val, int l, int r) { if (aint[val].lazy==0) return; aint[val].maxval+=aint[val].lazy; if (l!=r) { aint[val*2].lazy=aint[val].lazy; aint[val*2+1].lazy=aint[val].lazy; } aint[val].lazy=0; } void build(int l, int r, int val) { if (l==r) { aint[val].maxval=leaves[revstamp[l]]; aint[val].lazy=0; return; } int mid; mid=(l+r)/2; build(l,mid,val*2); build(mid+1,r,val*2+1); aint[val]=combine(aint[val*2],aint[val*2+1]); } void lazy_update(int l, int r, int val, int qa, int qb, int x) { prop(val,l,r); if (qa<=l && r<=qb) { aint[val].lazy+=x; return; } int mid; mid=(l+r)/2; if (qa<=mid) lazy_update(l,mid,val*2,qa,qb,x); if (qb>mid) lazy_update(mid+1,r,val*2+1,qa,qb,x); prop(val*2,l,mid); prop(val*2+1,mid+1,r); aint[val]=combine(aint[val*2],aint[val*2+1]); } int query(int l, int r, int val, int qa, int qb) { prop(val,l,r); if(qa<=l && r<=qb) { return aint[val].maxval; } int mid,ans; ans=0; mid=(l+r)/2; if (qa<=mid) ans=max(ans,query(l,mid,val*2,qa,qb)); if (qb>mid) ans=max(ans,query(mid+1,r,val*2+1,qa,qb)); return ans; } void add_path(int node, int delta) { while (pathend[node]!=root) { lazy_update(1,n,1,stamp[pathend[node]],stamp[node],delta); node=p[pathend[node]]; } lazy_update(1,n,1,stamp[pathend[node]],stamp[node],delta); } int rightmost_bigger(int l, int r, int val, int qa, int qb) { prop(val,l,r); if (l==r) return l; int mid; mid=(l+r)/2; prop(val*2,l,mid); prop(val*2+1,mid+1,r+1); if (aint[val*2+1].maxval>=3) return rightmost_bigger(mid+1,r,val*2+1,qa,qb); else return rightmost_bigger(l,mid,val*2,qa,qb); } void trim(int parent) { bool ok; ok=0; while (pathend[parent]!=root) { if (query(1,n,1,stamp[pathend[parent]],stamp[parent])>=3) { ok=1; break; } parent=p[pathend[parent]]; } if (query(1,n,1,stamp[pathend[parent]],stamp[parent])>=3) ok=1; if (ok) { int node; node=rightmost_bigger(1,n,1,stamp[pathend[parent]],stamp[parent]); while(revstamp[node]==0) { } trims.push_back(revstamp[node]); ans-=h[revstamp[node]]*2; add_path(revstamp[node],-2); } } void untrim() { for (auto x : trims) { add_path(x,2); ans+=h[x]*2; } trims.clear(); } } hevi; void dfs(int node, int parent) { leaves[node]=0; sz[node]=1; if (nodes[node].size()==1) { is_leaf[node]=1; ans+=h[node]; leaves[node]=1; return; } int mx; mx=0; for (auto x : nodes[node]) { if (x!=parent) { p[x]=node; h[x]=h[node]+1; dfs(x,node); leaves[node]+=leaves[x]; sz[node]+=sz[x]; if (sz[x]>sz[mx]) { mx=x; } } } heavychild[node]=mx; if (leaves[node]%2==1) { ans-=h[node]*(leaves[node]-1); leaves[node]=1; } else { ans-=h[node]*(leaves[node]-2); leaves[node]=2; } } void heavy_order(int node, int parent, int capat) { timer++; stamp[node]=timer; revstamp[timer]=node; pathend[node]=capat; if (heavychild[node]==0) return; heavy_order(heavychild[node],node,capat); for (auto x : nodes[node]) { if (x!=parent && x!=heavychild[node]) { heavy_order(x,node,x); } } } signed main() { /* ifstream fin("secvp.in"); ofstream fout("secvp.out"); */ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int q,i,j,uu,v,d,total_leaves; cin >> n >> q; for (i=1; i<=n-1; i++) { cin >> uu >> v; nodes[uu].push_back(v); nodes[v].push_back(uu); } for (i=1; i<=n; i++) { if (nodes[i].size()!=1) { root=i; break; } } h[root]=0; ans=0; dfs(root,-1); total_leaves=leaves[root]; timer=0; heavy_order(root,-1,root); hevi.build(1,n,1); for (i=1; i<=q; i++) { cin >> d; for (j=1; j<=d; j++) { cin >> u[j]; if (nodes[u[j]].size()!=1) { total_leaves++; ans+=h[u[j]]+1; } else { ans+=h[u[j]]+1; ans-=h[u[j]]; } if(nodes[u[j]].size()!=1) hevi.add_path(u[j],1); nodes[u[j]].push_back(n+j); } for (j=1; j<=d; j++) { hevi.trim(u[j]); } if (total_leaves%2==0) cout << ans << "\n"; else cout << "-1\n"; hevi.untrim(); for (j=1; j<=d; j++) { nodes[u[j]].pop_back(); if (nodes[u[j]].size()!=1) hevi.add_path(u[j],-1); if (nodes[u[j]].size()!=1) { total_leaves--; ans-=h[u[j]]+1; } else { ans-=h[u[j]]+1; ans+=h[u[j]]; } } } return 0; }