44 2021. 01. 08 20:34:52 mraron Spring cleaning cpp11 Elfogadva 100/100 495ms 70028 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 4ms 6572 KiB
2 Elfogadva 172ms 11020 KiB
subtask2 9/9
3 Elfogadva 75ms 8576 KiB
4 Elfogadva 8ms 8932 KiB
5 Elfogadva 112ms 26172 KiB
6 Elfogadva 145ms 24100 KiB
7 Elfogadva 178ms 29448 KiB
subtask3 9/9
8 Elfogadva 61ms 14168 KiB
9 Elfogadva 9ms 14628 KiB
10 Elfogadva 70ms 45388 KiB
11 Elfogadva 182ms 45292 KiB
12 Elfogadva 54ms 45548 KiB
subtask4 16/16
13 Elfogadva 116ms 22180 KiB
14 Elfogadva 71ms 21252 KiB
15 Elfogadva 25ms 21392 KiB
16 Elfogadva 18ms 22620 KiB
17 Elfogadva 23ms 23208 KiB
18 Elfogadva 85ms 23332 KiB
subtask5 19/19
19 Elfogadva 189ms 30392 KiB
20 Elfogadva 444ms 31820 KiB
21 Elfogadva 296ms 27640 KiB
22 Elfogadva 495ms 34200 KiB
23 Elfogadva 441ms 35588 KiB
subtask6 17/17
24 Elfogadva 432ms 44016 KiB
25 Elfogadva 177ms 51744 KiB
26 Elfogadva 330ms 52316 KiB
27 Elfogadva 146ms 57096 KiB
subtask7 30/30
28 Elfogadva 291ms 44956 KiB
29 Elfogadva 280ms 58740 KiB
30 Elfogadva 119ms 56344 KiB
31 Elfogadva 180ms 70028 KiB
32 Elfogadva 453ms 51692 KiB
33 Elfogadva 247ms 62180 KiB
34 Elfogadva 268ms 67708 KiB
35 Elfogadva 280ms 69460 KiB