Submission #1198107

#TimeUsernameProblemLanguageResultExecution timeMemory
1198107Dan4LifeRailway (BOI17_railway)C++20
100 / 100
143 ms32116 KiB
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;

const int mxN = (int)2e5+10;
const int INF = (int)1e9+1;
const ll LINF = (ll)2e18+1;
const int MOD = (int)1e9+7;
const int mxLg = 21;

int N, M, K, dfs_tim;
vector<ar2> adj[mxN];
int jmp[mxLg][mxN];
int st[mxN], en[mxN], sub[mxN];
int head[mxN], edg[mxN];

template<int SZ>
struct Fenwick{
	int fen[SZ];
	void init(){ memset(fen,0,sizeof(fen)); }
	void upd(int x, int v){
		for(x++; x<SZ; x+=x&-x) fen[x]+=v;
	}
	int sum(int x){
		int s = 0;
		for(x++; x>0; x-=x&-x) s+=fen[x];
		return s;
	}
};
Fenwick<mxN> fen;

bool isAnc(int a, int b){
	return st[a]<=st[b] and en[a]>=en[b];
}

int lca(int a, int b){
	if(isAnc(a,b)) return a;
	if(isAnc(b,a)) return b;
	for(int i = mxLg-1; i>=0; i--)
		if(jmp[i][a] and !isAnc(jmp[i][a],b))
			a = jmp[i][a];
	return jmp[0][a];
}

void dfs(int s, int p){
	sub[s] = 1; jmp[0][s] = p; 
	for(int j = 0; j < sz(adj[s]); j++){
		auto [u,w] = adj[s][j];
		if(u==p) continue;
		dfs(u,s); sub[s]+=sub[u];
		if(adj[s][0][0]==p or sub[adj[s][0][0]]<sub[u])
			swap(adj[s][0],adj[s][j]);
	}
}

void dfsHld(int s, int p, int h){
	st[s] = ++dfs_tim; head[s] = h;
	for(auto [u,w] : adj[s]){
		if(u==p) continue; edg[u]=w;
		dfsHld(u,s,adj[s][0][0]==u?h:u); 
	}
	en[s] = dfs_tim;
}

void upd(int x, int y, int v){
	while(head[x]!=head[y]){
		fen.upd(st[head[y]],v);
		fen.upd(st[y]+1,-v);
		y = jmp[0][head[y]];
	}
	fen.upd(st[x],v);
	fen.upd(st[y]+1,-v);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N >> M >> K; fen.init();
	
	for(int i = 1; i < N; i++){
		int a, b; cin >> a >> b;
		adj[a].pb({b,i}); adj[b].pb({a,i});
	}
	
	dfs(1,0); dfsHld(1,0,1);
	for(int j = 1; j < mxLg; j++)
		for(int i = 1; i <= N; i++)
			jmp[j][i] = jmp[j-1][jmp[j-1][i]];
	
	while(M--){
		int n, x; vi v; v.clear(); cin >> n;
		for(int i = 0; i < n; i++) cin >> x, v.pb(x);
		sort(all(v),[&](int a, int b){ return st[a]<st[b]; });
		for(int i = 1; i < n; i++) v.pb(lca(v[i-1],v[i]));
		sort(all(v),[&](int a, int b){ return st[a]<st[b]; });
		v.erase(unique(all(v)),end(v));
		for(int i = 1; i < sz(v); i++){
			int l = lca(v[i-1],v[i]), x = v[i];
			for(int i = mxLg-1; i>=0; i--)
				if(jmp[i][x] and !isAnc(jmp[i][x],l))
					x = jmp[i][x];
			upd(x,v[i],1);
		}
	}
	set<int> S;
	for(int i = 2; i <= N; i++)
		if(fen.sum(st[i])>=K) S.insert(edg[i]);
	cout << sz(S) << "\n";
	for(auto u : S) cout << u << " ";
	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...