442021-01-08 20:34:52mraronSpring cleaningcpp11Accepted 100/100495ms70028 KiB
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
#include<random>
#include<bitset>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

#ifndef ONLINE_JUDGE
#  define LOG(x) (cerr << #x << " = " << (x) << endl)
#else
#  define LOG(x) ((void)0)
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=acos(-1);
const ll INF = 1LL<<62;
const ll MINF = -(1LL<<62);

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int>(0, n-1)(rng)

const int MAXN=100001, hgt=18;

int tr[4*MAXN]; //count of even
int lz[4*MAXN]; 
int n,q;
vector<int> adj[MAXN];
void build(int ind, int L, int R) {
	if(L==R) {
		tr[ind]=1;
		lz[ind]=0;
	}else {
		build(2*ind, L, (L+R)/2);
		build(2*ind+1, (L+R)/2+1, R);
		tr[ind]=tr[2*ind]+tr[2*ind+1];
		lz[ind]=0;
	}
}

void push(int ind, int L, int R) {
	lz[ind]%=2;
	if(lz[ind]!=0) {
		tr[ind]=(R-L+1)-tr[ind];
		if(L!=R) {
			lz[2*ind]+=lz[ind];
			lz[2*ind+1]+=lz[ind];
		}
		lz[ind]=0;
	}
}

int query(int ind, int L, int R, int i, int j) {
	push(ind, L, R);
	if(R<i || j<L) return 0;
	if(i<=L && R<=j) return tr[ind];
	return query(2*ind, L, (L+R)/2, i, j)+query(2*ind+1, (L+R)/2+1, R, i, j);
}

void incr(int ind, int L, int R, int i, int j, int by=1) {
	push(ind, L, R);
	if(R<i || j<L) return ;
	if(i<=L && R<=j) {
		lz[ind]+=by;
		push(ind, L, R);
		return ;
	}
	
	incr(2*ind, L, (L+R)/2, i, j, by);
	incr(2*ind+1, (L+R)/2+1, R, i, j, by);
	
	tr[ind]=tr[2*ind]+tr[2*ind+1];
}


// to make it compatible with hld implementation we also calculate sz
int par[MAXN], b[MAXN], lvl[MAXN], sz[MAXN];
int dp[MAXN][hgt];

void dfs_lca(int x) {
	b[x]=1;
	sz[x]=1;
	
	for(auto i:adj[x]) {
		if(!b[i]) {
			par[i]=x;
			lvl[i]=lvl[x]+1;
			dfs_lca(i);
			sz[x]+=sz[i];
		}
	}
	
	b[x]=2;
}

int pos[MAXN];
int root[MAXN];

int curr_pos=0;
void hld(int x, int id) {
	pos[x]=curr_pos++;
	root[x]=id;
	
	int best_child=-1;
	for(auto i_:adj[x]) {
		auto i=i_;
		if(par[x]!=i) {
			if(best_child==-1 || sz[best_child]<sz[i]) {
				best_child=i;
			}
		}
	}
	
	if(best_child==-1) {
		return ;
	}
	
	hld(best_child, id);
	
	for(auto i_:adj[x]) {
		auto i=i_;
		if(par[x]==i || i==best_child) continue ;
		hld(i, i);
	}
}

int query_up(int up, int down, int by) {
	int ans=0;
	
	while(1) {
		//~ cerr<<up<<" "<<down<<"\n";
		if(root[up]==root[down]) {
			incr(1,0,n-1,pos[up],pos[down],by);
			break ;
		}else {
			incr(1,0,n-1,pos[root[down]],pos[down],by);
			down=par[root[down]];
		}
	}
	return ans;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	n=getint<int>();
	q=getint<int>();
	for(int i=1;i<n;++i) {
		int a,b;
		a=getint<int>();
		b=getint<int>();
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
		
	dfs_lca(1);
	hld(1,1);
	build(1,0,n-1);
	
	int leaves=0;
	for(int i=1;i<=n;++i) {
		if((int)adj[i].size()==1) {
			leaves++;
			query_up(1,i,1);
		}
	}
	
	vector<int> add(n+1), add2(n+1);
	for(int i=0;i<q;++i) {
		int cnt;
		cnt=getint<int>();
		vector<int> lst(cnt);
		for(int j=0;j<cnt;++j) {
			lst[j]=getint<int>();
			add[lst[j]]++;
			if((int)adj[lst[j]].size()==1 && add[lst[j]]==1) {
				leaves--;
			}
			leaves++;
		}
		
		if(leaves&1) {
			cout<<"-1\n";
		}else {
			for(int j=0;j<cnt;++j) {
				add2[lst[j]]++;
				if((int)adj[lst[j]].size()==1 && add2[lst[j]]==1) {
					
				}else {
					query_up(1,lst[j],1);
				}
			}
			int ans=n-1+cnt+query(1,0,n-1,1,n-1);
			cout<<ans<<"\n";
			for(int j=0;j<cnt;++j) {
				add2[lst[j]]--;
				if((int)adj[lst[j]].size()+add2[lst[j]]==1) {
					
				}else {
					query_up(1,lst[j],-1);
				}
			}
		}
		
		for(int j=0;j<cnt;++j) {
			add[lst[j]]--;
			if((int)adj[lst[j]].size()+add[lst[j]]==1) {
				leaves++;
			}
			leaves--;
		}
	}


	
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms6572 KiB
2Accepted172ms11020 KiB
subtask29/9
3Accepted75ms8576 KiB
4Accepted8ms8932 KiB
5Accepted112ms26172 KiB
6Accepted145ms24100 KiB
7Accepted178ms29448 KiB
subtask39/9
8Accepted61ms14168 KiB
9Accepted9ms14628 KiB
10Accepted70ms45388 KiB
11Accepted182ms45292 KiB
12Accepted54ms45548 KiB
subtask416/16
13Accepted116ms22180 KiB
14Accepted71ms21252 KiB
15Accepted25ms21392 KiB
16Accepted18ms22620 KiB
17Accepted23ms23208 KiB
18Accepted85ms23332 KiB
subtask519/19
19Accepted189ms30392 KiB
20Accepted444ms31820 KiB
21Accepted296ms27640 KiB
22Accepted495ms34200 KiB
23Accepted441ms35588 KiB
subtask617/17
24Accepted432ms44016 KiB
25Accepted177ms51744 KiB
26Accepted330ms52316 KiB
27Accepted146ms57096 KiB
subtask730/30
28Accepted291ms44956 KiB
29Accepted280ms58740 KiB
30Accepted119ms56344 KiB
31Accepted180ms70028 KiB
32Accepted453ms51692 KiB
33Accepted247ms62180 KiB
34Accepted268ms67708 KiB
35Accepted280ms69460 KiB