#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN=1e5+5;
const int MAXQ=1e5+5;
const int MAXLOG=21;
int n,q;
vector<int> adj[MAXN];
bool leaf[MAXN];
int root=1;
int subLf[MAXN];
int depth[MAXN];
int cnt1[MAXN], cnt2[MAXN];
int ansOrg=0;
int tin[MAXN];
int order[2*MAXN];
int timer=0;
int lg2[2*MAXN];
int spT[2*MAXN][MAXLOG];
unordered_set<int> s;
int newCnt[MAXN];
vector<int> virtNodes;
vector<int> vAdj[MAXN];
int used[MAXN];
void dfs(int v,int par,int d)
{
depth[v]=d;
subLf[v]=0;
if(leaf[v]) subLf[v]=1;
for(auto u: adj[v])
{
if(u==par) continue;
dfs(u,v,d+1);
subLf[v]+=subLf[u];
}
}
void dfs2(int v,int par)
{
if(subLf[v]%2==1) cnt1[v]++;
else cnt2[v]++;
for(auto u: adj[v])
{
if(u==par) continue;
cnt1[u]=cnt1[v];
cnt2[u]=cnt2[v];
dfs2(u,v);
}
}
void dfs3(int v,int par)
{
order[++timer]=v;
tin[v]=timer;
for(auto u: adj[v])
{
if(u==par) continue;
dfs3(u,v);
order[++timer]=v;
}
}
void sparseTable()
{
lg2[0]=-1;
for(int i=1;i<=timer;i++)
{
lg2[i]=lg2[i/2]+1;
spT[i][0]=order[i];
}
for(int j=1;(1<<j)<=timer;j++)
{
for(int i=1;i<=timer;i++)
{
if(i+(1<<(j-1))>timer) break;
spT[i][j]=spT[i][j-1];
if(depth[spT[i+(1<<(j-1))][j-1]]<depth[spT[i][j-1]]) spT[i][j]=spT[i+(1<<(j-1))][j-1];
}
}
}
int lca(int u,int v)
{
if(tin[u]>tin[v]) swap(u,v);
int d=tin[v]-tin[u]+1;
int c1=spT[tin[u]][lg2[d]];
int c2=spT[tin[v]-(1<<lg2[d])+1][lg2[d]];
if(depth[c1]<=depth[c2]) return c1;
return c2;
}
bool cmp(int u,int v)
{
return tin[u]<tin[v];
}
int buildVirtTree()
{
for(auto v: virtNodes) used[v]=1;
sort(virtNodes.begin(), virtNodes.end(), cmp);
int sz=virtNodes.size();
for(int i=1;i<sz;i++)
{
virtNodes.push_back(lca(virtNodes[i-1], virtNodes[i]));
}
sort(virtNodes.begin(), virtNodes.end(), cmp);
vector<int> nodes;
for(auto v: virtNodes)
{
if(!nodes.empty() && nodes.back()!=v) nodes.push_back(v);
if(nodes.empty()) nodes.push_back(v);
}
for(auto v: nodes) vAdj[v].clear();
vector<int> st;
for(auto v: nodes)
{
while(!st.empty() && lca(st.back(), v)!=st.back()) st.pop_back();
if(!st.empty())
{
vAdj[st.back()].push_back(v);
}
st.push_back(v);
return st[0];
}
pair<int,int> dfs_virt(int v,int par)
{
int ret=0;
int cntUsed=0;
if(used[v]) cntUsed=1;
for(auto u: vAdj[v])
{
auto cur=dfs_virt(u,v);
ret+=cur.first;
cntUsed+=cur.second;
}
if(cntUsed%2==1 && par!=-1)
{
int cntOdd=cnt1[v]-cnt1[par];
int cntEv=cnt2[v]-cnt2[par];
ret+=cntOdd-cntEv;
}
return {ret, cntUsed};
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>q;
for(int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
if(adj[i].size()==1) leaf[i]=1;
else root=i;
}
dfs(root,-1,1);
dfs2(root,-1);
dfs3(root,-1);
sparseTable();
for(int i=1;i<=n;i++)
{
if(i==root) continue;
if(subLf[i]%2==1) ansOrg+=1;
else ansOrg+=2;
}
for(int tt=0;tt<q;tt++)
{
int d;
cin>>d;
for(int i=0;i<d;i++)
{
int v;
cin>>v;
newCnt[v]++;
s.insert(v);
}
int ans=ansOrg+d;
for(auto v: s)
{
if(leaf[v]) newCnt[v]--;
if(newCnt[v]%2==1) virtNodes.push_back(v);
}
if((subLf[root]+virtNodes.size())%2==1) cout<<-1<<endl;
else
{
if(virtNodes.size()>0)
{
int virtRoot=buildVirtTree();
ans+=dfs_virt(virtRoot,root).first;
for(auto v: virtNodes) used[v]=0;
}
cout<<ans<<endl;
}
for(auto v: s) newCnt[v]=0;
s.clear();
virtNodes.clear();
}
return 0;
}
Compilation message
cleaning.cpp: In function 'int buildVirtTree()':
cleaning.cpp:144:1: error: a function-definition is not allowed here before '{' token
144 | {
| ^
cleaning.cpp:166:1: error: a function-definition is not allowed here before '{' token
166 | {
| ^
cleaning.cpp:238:1: error: expected '}' at end of input
238 | }
| ^
cleaning.cpp:109:1: note: to match this '{'
109 | {
| ^
cleaning.cpp:121:17: warning: control reaches end of non-void function [-Wreturn-type]
121 | vector<int> nodes;
| ^~~~~
