Submission #1299011

#TimeUsernameProblemLanguageResultExecution timeMemory
1299011PieArmySpring cleaning (CEOI20_cleaning)C++20
0 / 100
1094 ms327680 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

int n,q;
vector<int>komsu[100023];
int dep[100023],sub[100023],cnt[100023],ust[100023],par[100023];
int leaf[100023];
int in[100023],out[100023];
int sira[100023];
int tim=0;
int pref[100023];
int ans=0;
int root=0;
vector<int>child[100023];
int val[100023];
map<int,int>mp;

void predfs(int pos){
	sub[pos]=1;
	cnt[pos]=0;
	for(int x:komsu[pos]){
		if(x==par[pos])continue;
		dep[x]=dep[pos]+1;
		par[x]=pos;
		predfs(x);
		cnt[pos]+=cnt[x];
		sub[pos]+=sub[x];
	}
	if(!cnt[pos]){
		leaf[pos]=1;
		cnt[pos]=1;
	}
}

void dfs(int pos){
	int mx=-1;
	in[pos]=++tim;
	sira[in[pos]]=pos;
	pref[in[pos]]=pref[in[pos]-1];
	if(par[pos])pref[in[pos]]+=(cnt[pos]&1)*2-1;
	if(par[pos])ans+=!(cnt[pos]&1);
	for(int x:komsu[pos]){
		if(x==par[pos])continue;
		if(mx==-1||sub[x]>sub[mx])mx=x;
	}
	if(mx!=-1){
		ust[mx]=ust[pos];
		dfs(mx);
		for(int x:komsu[pos]){
			if(x==par[pos]||x==mx)continue;
			ust[x]=pos;
			dfs(x);
		}
	}
	out[pos]=tim;
}

int cal(int from,int tar){
	int res=0;
	while(dep[ust[from]]>dep[tar]){
		res+=pref[in[from]]-pref[in[ust[from]]];
		from=ust[from];
	}
	res+=pref[in[from]]-pref[in[tar]];
	return res;
}

int gez(int pos){
	int res=0;
	for(int x:child[pos]){
		res+=gez(x);
		val[pos]+=val[x];
		if(val[x]&1){
			res+=cal(x,pos);
		}
	}
	child[pos].clear();
	return res;
}

int lca(int a,int b){
	while(ust[a]!=ust[b]){
		while(dep[ust[a]]<dep[ust[b]])b=ust[b];
		swap(a,b);
	}
	if(dep[a]<dep[b])swap(a,b);
	if(in[b]<=in[a]&&out[b]>=in[a])return b;
	return ust[b];
}

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>q;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		komsu[x].pb(y);
		komsu[y].pb(x);
	}
	root=1;
	while(komsu[root].size()==1)root++;
	dep[root]=1;
	predfs(root);
	dfs(root);
	while(q--){
		int m;
		mp.clear();
		cin>>m;
		for(int i=0;i<m;i++){
			int x;cin>>x;
			mp[in[x]]++;
		}
		vector<int>v;
		for(auto&[a,b]:mp){
			v.pb(sira[a]);
			b-=leaf[sira[a]];
		}
		int s=v.size();
		for(int i=1;i<s;i++){
			int lc=lca(v[i-1],v[i]);
			if(mp.count(lc)==0){
				mp[in[lc]]=0;
				v.pb(lc);
			}
		}
		sort(v.begin(),v.end(),[&](const int &x,const int &y){
			return in[x]<in[y];
		});
		for(auto[a,b]:mp){
			val[sira[a]]=b;
		}
		vector<int>sta={v[0]};
		s=v.size();
		for(int i=1;i<s;i++){
			while(in[v[i]]>out[sta.back()])sta.pop_back();
			child[sta.back()].pb(v[i]);
			sta.pb(v[i]);
		}
		int res=gez(v[0]);
		if((val[v[0]]+cnt[root])&1){
			cout<<-1<<endl;
			continue;
		}
		if(val[v[0]]&1)res+=cal(v[0],root);
		cout<<ans+res+n-1+m<<endl;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...