#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
#define printl(args...) printf(args)
#else
#define printl(args...) 0
#endif
int n,q;
vector<int>g[100001];
int leaves[100001],tot_leaves,bad;
bool is_leaf[100001];
int tin[100001],tout[100001],timer,up[100001][18];
vector<int>g2[100001];
int ans,bit[100001];
int a[100001],l_delta[100001];
void update(int pos,int val){for(;pos<=n;pos+=pos&-pos)bit[pos]+=val;}
int query(int l,int r,int res=0){res=0;for(;r;r-=r&-r)res+=bit[r];for(l--;l;l-=l&-l)res-=bit[l];return res;}
void lca_dfs(int node,int p=0){
tin[node]=++timer;
for(int i=1;i<18;i++)up[node][i]=up[up[node][i-1]][i-1];
if(g[node].size()==1){
leaves[node]=1;
tot_leaves++;
is_leaf[node]=true;
}
for(int i:g[node])if(i!=p){
up[i][0]=node;
lca_dfs(i,node);
leaves[node]+=leaves[i];
}
tout[node]=timer;
if(leaves[node]&1)update(tin[node],1),update(tout[node]+1,-1);
else{
update(tin[node],-1),update(tout[node]+1,1);
bad++;
}
}
bool upper(int u, int v){return tin[u]<=tin[v]&&tout[u]>=tout[v];}
int lca(int u, int v){
if(upper(u,v))return u;
for(int i=17;~i;i--)if(up[u][i]&&!upper(up[u][i],v))u=up[u][i];
return up[u][0];
}
void g2_dfs(int node,int p=0){
for(int i:g2[node])if(i!=p){
g2_dfs(i,node);
l_delta[node]+=l_delta[i];
}
ans+=(l_delta[node]&1)*query(tin[p]+1,tin[node]);
}
bool cmp(int u,int v){return tin[u]<tin[v];}
int main(){
scanf("%d%d",&n,&q);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++)if(g[i].size()>1){
lca_dfs(i);
break;
}
while(q--){
int d;
scanf("%d",&d);
vector<int>nodes;
for(int i=0;i<d;i++){
scanf("%d",&a[i]);
if(is_leaf[a[i]])is_leaf[a[i]]=false;
else{
leaves[a[i]]++;
tot_leaves++;
l_delta[a[i]]++;
nodes.push_back(a[i]);
}
}
sort(nodes.begin(),nodes.end(),cmp);
int m=nodes.size();
for(int i=1;i<m;i++)nodes.push_back(lca(nodes[i-1],nodes[i]));
sort(nodes.begin(),nodes.end(),cmp);
nodes.erase(unique(nodes.begin(),nodes.end()),nodes.end());
vector<int>stck;
for(int i:nodes){
while(stck.size()>1&&!upper(stck.back(),i)){
g2[stck[stck.size()-2]].push_back(stck.back());
stck.pop_back();
}
stck.push_back(i);
}
while(stck.size()>1){
g2[stck[stck.size()-2]].push_back(stck.back());
stck.pop_back();
}
if(tot_leaves&1)puts("-1");
else{
ans=m+d+bad-2;
if(stck.size())g2_dfs(stck[0]);
printf("%d\n",ans);
}
for(int i=0;i<d;i++){
if(leaves[a[i]]==1)is_leaf[a[i]]=true;
else{
leaves[a[i]]--;
tot_leaves--;
}
}
for(int i:nodes){
g2[i].clear();
l_delta[i]=0;
}
}
}
Compilation message
cleaning.cpp: In function 'int main()':
cleaning.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d%d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~
cleaning.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d%d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~
cleaning.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d",&d);
| ~~~~~^~~~~~~~~
cleaning.cpp:81:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
6900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
7432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
8416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
88 ms |
13260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
17864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
