Submission #1348932

#TimeUsernameProblemLanguageResultExecution timeMemory
1348932Rawlat_vanakRailway (BOI17_railway)C++20
100 / 100
72 ms40156 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back


vector<vector<int>> graph,up;
vector<int> tin,depth,ans,cnt;
int tyme;

void dfs(int u, int p){
	tyme++;
	tin[u]=tyme;
	up[u][0]=p;
	depth[u]=depth[p]+1;
	for(int i=1;i<21;i++){
		up[u][i]=up[up[u][i-1]][i-1];
	}
	for(int v:graph[u]){
		if(v==p) continue;
		dfs(v,u);
	}
}

int lca(int u, int v){
	if(depth[u]>depth[v]){
		swap(u,v);
	}
	int d=depth[v]-depth[u];
	for(int i=20;i>=0;i--){
		if(d&(1<<i)){
			v=up[v][i];
		}
	}
	if(u==v){
		return u;
	}

	for(int i=20;i>=0;i--){
		if(up[u][i]!=up[v][i]){
			u=up[u][i];
			v=up[v][i];
		}
	}
	return up[u][0];
}

void dfs2(int u, int p){
	ans[u]+=cnt[u];
	for(int v:graph[u]){
		if(v==p){
			continue;
		}
		dfs2(v,u);
		ans[u]+=ans[v];
	}

}


int32_t main(){
	speedIO;
	int t,n,m,k,q;
	//cin>>t;
	
	t=1;
	while(t--){
		cin>>n>>m>>k;
		graph.clear();
		graph.resize(n+1);
		tin.clear();
		tin.resize(n+1);
		up.clear();
		up.resize(n+1, vector<int>(21));
		depth.clear();
		depth.resize(n+1,0);
		vector<pii> edges(n-1);
		cnt.clear();
		cnt.resize(n+1,0);
		ans.clear();
		ans.resize(n+1,0);
		for(int i=0;i<n-1;i++){
			int u,v;
			cin>>u>>v;
			graph[u].pb(v);
			graph[v].pb(u);
			edges[i]={u,v};
		}
		tyme=0;
		tin[0]=0;
		dfs(1,0);
		vector<int> eees(n+1);
		for(int i=0;i<n-1;i++){
			int u=edges[i].f,v=edges[i].s;
			if(u==up[v][0]){
				eees[v]=i+1;
			}else{
				eees[u]=i+1;
			}
		}
		



		while(m--){
			int x;
			cin>>x;
			vector<pii> a(x);
			for(int i=0;i<x;i++){
				cin>>a[i].s;
				a[i].f=tin[a[i].s];
				cnt[a[i].s]++;
			}
			sort(a.begin(),a.end());
			for(int i=0;i<x;i++){
				int u=lca(a[i].s,a[(i+1)%x].s);
				//cout<<a[i].s<<' '<<u<<'\n';
				cnt[u]--;
			}


		}
		dfs2(1,0);
		vector<int> blah;
		for(int i=1;i<=n;i++){
			if(ans[i]>=k){
				blah.pb(eees[i]);
			}
		}

		
		cout<<blah.size()<<'\n';
		sort(blah.begin(),blah.end());
		for(int i:blah){
			cout<<i<<' ';
		}


		













	}






		

	
	return 0;
}
#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...