#include <bits/stdc++.h>
//#define int ll
#define MAX 1000001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define outputar(a,b){\
for(int i=0;i<b;i++){\
cout << a[i] << " ";\
}\
cout << "\n";\
}
#define outputvec(a){\
for(auto x:a){\
cout << (int)x << " ";\
}\
cout << endl;\
}
#define reset(a,n,v){\
for(int i=0;i<n;i++){\
a[i]=v;\
}\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
freopen((filename+".in").c_str(),"r",stdin);
freopen((filename+".out").c_str(),"w",stdout);
}
int n,q,t=1,m,k,x,y,z,x2,y2,z2,a[MAX],b[MAX],c[MAX],in[MAX],out[MAX],e[MAX],tim;
ll res;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string s[MAX],str[1];
//int e[1001][1001];
//bool e1[1001][1001];
string s1,s2,s3;
const int mod = 998244353;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
vector<vector<int>> g;
void dfs(int v,int prev){
in[v]=++tim;
c[v]=(g[v].size()==1);
for(auto x:g[v]){
if(x==prev){
continue;
}
dfs(x,v);
c[v]+=c[x];
}
out[v]=tim;
}
struct segtree{
vector<int> sums;
vector<int> lazy;
int sz=0;
void init(int n){
sz=1;
while(sz<n){
sz*=2;
}
sums.resize(2*sz,0);
lazy.resize(2*sz,0);
}
void build(int x,int lx,int rx,vector<int> &a){
if(rx-lx==1){
if(lx<(int)a.size()){
sums[x]=a[lx];
}
return;
}
int mid=(lx+rx)/2;
build(2*x+1,lx,mid,a);
build(2*x+2,mid,rx,a);
sums[x]=sums[2*x+1]+sums[2*x+2];
}
void build(vector<int> &a){
build(0,0,sz,a);
}
void propogate(int x,int lx,int rx){
if(rx-lx==1 || !lazy[x]){
return;
}
int mid=(lx+rx)/2;
sums[2*x+1]=mid-lx-sums[2*x+1];
sums[2*x+2]=rx-mid-sums[2*x+2];
lazy[2*x+1]^=1;
lazy[2*x+2]^=1;
lazy[x]=0;
}
void upd(int x,int lx,int rx,int l,int r){
propogate(x,lx,rx);
if(lx>=r || rx<=l){
return;
}
if(lx>=l && rx<=r){
sums[x]=rx-lx-sums[x];
lazy[x]^=1;
return;
}
int mid=(lx+rx)/2;
upd(2*x+1,lx,mid,l,r);
upd(2*x+2,mid,rx,l,r);
sums[x]=sums[2*x+1]+sums[2*x+2];
}
void upd(int l,int r){
if(l==n){
return;
}
upd(0,0,sz,l,r);
}
int get_sum(int x,int lx,int rx,int l,int r){
propogate(x,lx,rx);
if(lx>=r || rx<=l){
return 0;
}
if(lx>=l && rx<=r){
return sums[x];
}
int mid=(lx+rx)/2;
int s1=get_sum(2*x+1,lx,mid,l,r);
int s2=get_sum(2*x+2,mid,rx,l,r);
return s1+s2;
}
int get_sum(int l,int r){
return get_sum(0,0,sz,l,r);
}
};
void solve(){
cin >> n >> q;
g.clear();
g.resize(n+1);
for(int i=0;i<n-1;i++){
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
tim=-1;
dfs(1,-1);
vector<int> d(n);
for(int i=1;i<=n;i++){
d[in[i]]=1-c[i]%2;
}
set<int> f;
segtree st;
st.init(n);
st.build(d);
for(int i=0;i<q;i++){
cin >> m;
f.clear();
int cnt=0;
for(int j=1;j<=m;j++){
cin >> e[j];
x=e[j];
if(g[e[j]].size()!=1 || f.find(e[j])!=f.end()){
st.upd(in[x]+1,out[x]+1);
cnt++;
}
f.ins(e[j]);
}
if(cnt%2){
st.upd(0,n);
}
if(st.get_sum(in[1],in[1]+1)==0){
cout << -1 << "\n";
}
else{
cout << st.get_sum(0,n)+n+m-2 << "\n";
}
f.clear();
cnt=0;
for(int j=1;j<=m;j++){
x=e[j];
if(g[e[j]].size()!=1 || f.find(e[j])!=f.end()){
st.upd(in[x]+1,out[x]+1);
cnt++;
}
f.ins(e[j]);
}
if(cnt%2){
st.upd(0,n);
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//cin >> t;
ll cnt1=1;
while(t--){
solve();
}
}
Compilation message
cleaning.cpp: In function 'int main()':
cleaning.cpp:205:8: warning: unused variable 'cnt1' [-Wunused-variable]
205 | ll cnt1=1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
39600 KB |
Output is correct |
| 2 |
Incorrect |
71 ms |
44304 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
42428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
43092 KB |
Output is correct |
| 2 |
Correct |
79 ms |
43088 KB |
Output is correct |
| 3 |
Correct |
47 ms |
60500 KB |
Output is correct |
| 4 |
Correct |
174 ms |
62292 KB |
Output is correct |
| 5 |
Correct |
38 ms |
59020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
44636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
50000 KB |
Output is correct |
| 2 |
Incorrect |
81 ms |
50000 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
54088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
39600 KB |
Output is correct |
| 2 |
Incorrect |
71 ms |
44304 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
