제출 #1352184

#제출 시각아이디문제언어결과실행 시간메모리
1352184jumpRailway (BOI17_railway)C++20
0 / 100
88 ms33268 KiB
#include <bits/stdc++.h>
#define int long long

std::vector<std::pair<int,int>> adj[100010];
std::vector<int> ans;
int n,m,k;
int diff[100010];
int depth[100010];
int cid=0;
int id[100010];
int mxid[100010];
int arr[100010];
int bilift[100010][23];
void construct(int curr,int par){
	mxid[curr]=id[curr]=cid++;
	depth[curr]=depth[par]+1;
	if(curr==1){
		for(int i=1;i<=20;i++){
			bilift[curr][i]=1;
		}
	}
	else{
		bilift[curr][0]=par;
		for(int i=1;i<=20;i++){
			bilift[curr][i]=bilift[bilift[curr][i-1]][i-1];
		}
	}
	for(auto [to,idx]:adj[curr]){
		if(to==par)continue;
		mxid[curr]=std::max(mxid[curr],mxid[curr]);
		construct(to,curr);
	}
}
void dfs(int curr,int par,int req){
	req+=diff[curr];
	for(auto [to,idx]:adj[curr]){
		if(to==par)continue;
		if(req>=k)ans.push_back(idx);
		dfs(to,curr,req);
	}
}
int lca(int n1,int n2){
	if(depth[n2]>depth[n1])std::swap(n1,n2);
	for(int i=20;i>=0;i--){
		if(depth[bilift[n1][i]]>=depth[n2])n1=bilift[n1][i];
	}
	if(n1==n2)return n1;
	for(int i=20;i>=0;i--){
		if(bilift[n1][i]!=bilift[n2][i])n1=bilift[n1][i],n2=bilift[n2][i];
	}
	return bilift[n1][0];
}
signed main() {
	std::cin >> n >> m >> k;
	for(int i=0;i<n-1;i++){
		int in1,in2;
		std::cin >> in1 >> in2;
		adj[in1].push_back({in2,i});
		adj[in2].push_back({in1,i});
	}
	construct(1,1);
	for(int i=0;i<m;i++){
		std::set<std::pair<std::pair<int,int>,int>> st;
		int amt;
		std::cin >> amt;
		int aLca;
		std::cin >> aLca;
		st.insert({{id[aLca],mxid[aLca]},aLca});
		for(int i=1;i<amt;i++){
			int in;
			std::cin >> in;
			aLca=lca(aLca,in);
			auto itr=st.upper_bound({{id[in],(int)-1e18},(int)-1e18});
			auto itr2=itr;
			if(itr2!=st.begin()){
				itr2--;
				if(itr2->first.second>=mxid[in]){
					st.erase(itr2);
				}
			}
			if(itr!=st.end()&&itr->first.second<=mxid[in]){
				st.insert({{id[in],mxid[in]},in});
			}
		}
		diff[aLca]+=1;
		for(auto [p,idx]:st){
			diff[idx]-=1;
		}
	}
	dfs(0,0,0);
	std::sort(ans.begin(),ans.end());
	std::cout << ans.size() << '\n';
	for(auto edge:ans)std::cout << edge << ' ';
}
#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...