제출 #230891

#제출 시각아이디문제언어결과실행 시간메모리
230891eohomegrownappsRailway (BOI17_railway)C++14
23 / 100
1099 ms38360 KiB
#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int,int>>> adjlist;
vector<int> depth;
vector<set<int>> sets;
vector<int> loc;
vector<vector<int>> nadd;
vector<vector<int>> nremove;
vector<int> ans;
int pk[100000][20];
int n,k;

void dfs(int node, int parent){
	for (auto p : adjlist[node]){
		if (p.first==parent){continue;}
		int i=p.first;
		pk[i][0]=node;
		depth[i]=depth[node]+1;
		dfs(i,node);
	}
}

void decom2k(){
	for (int i = 1; i<20; i++){
		for (int j = 0; j<n; j++){
			if (pk[j][i-1]!=-1){
				pk[j][i]=pk[pk[j][i-1]][i-1];
			}
		}
	}
}

int lca(int a, int b){
	//wlog a deeper
	if (depth[b]>depth[a]){
		swap(a,b);
	}
	for (int i = 19; i>=0; i--){
		if (pk[a][i]==-1){continue;}
		if (depth[pk[a][i]]>=depth[b]){
			a=pk[a][i];
		}
	}
	if (a==b){
		return a;
	}
	for (int i = 19; i>=0; i--){
		if (pk[a][i]==-1){continue;}
		if (pk[a][i]!=pk[b][i]){
			a=pk[a][i];b=pk[b][i];
		}
	}
	return pk[a][0];
}

void setdfs(int node, int parent){
	if (parent!=-1&&adjlist[node].size()==1&&adjlist[node][0].first==parent){
		for (int i : nadd[node]){
			sets[loc[node]].insert(i);
		}
		for (int i : nremove[node]){
			sets[loc[node]].erase(i);
		}
		return;
	}
	int largestset = -1;
	int largestnode = -1;
	for (auto p : adjlist[node]){
		if (p.first==parent){continue;}
		setdfs(p.first,node);
		int s = sets[loc[p.first]].size();
		if (s>=k){
			ans.push_back(p.second);
		}
		if (s>largestset){
			largestnode=p.first;
			largestset=s;
		}
	}
	for (auto p : adjlist[node]){
		if (p.first==parent){continue;}
		if (p.first==largestset){continue;}
		for (int i : sets[loc[p.first]]){
			sets[loc[largestnode]].insert(i);
		}
	}
	loc[node]=loc[largestnode];
	for (int i : nadd[node]){
		sets[loc[node]].insert(i);
	}
	for (int i : nremove[node]){
		sets[loc[node]].erase(i);
	}
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int m;
	cin>>n>>m>>k;
	adjlist.resize(n);
	depth.resize(n,0);
	nadd.resize(n);
	nremove.resize(n);
	sets.resize(n);
	loc.resize(n);
	for (int i = 0; i<n-1; i++){
		loc[i]=i;
		int a,b;
		cin>>a>>b;
		a--;b--;
		adjlist[a].push_back({b,i});
		adjlist[b].push_back({a,i});
	}
	loc[n-1]=n-1;
	pk[0][0]=-1;
	dfs(0,-1);
	decom2k();
	for (int i = 0; i<m; i++){
		int num;
		cin>>num;
		int prevlca = -1;
		for (int j = 0; j<num; j++){
			int x;
			cin>>x;
			x--;
			nadd[x].push_back(i);
			if (prevlca==-1){
				prevlca=x;
			} else {
				prevlca=lca(prevlca,x);
			}
		}
		//cout<<prevlca<<endl;
		nremove[prevlca].push_back(i);
	}
	setdfs(0,-1);
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<'\n';
	for (int i : ans){
		cout<<i+1<<" ";
	}cout<<'\n';
}
#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...