제출 #1342699

#제출 시각아이디문제언어결과실행 시간메모리
1342699tkm_algorithmsRailway (BOI17_railway)C++20
100 / 100
153 ms47364 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using P = pair<int, int>;
//#define int ll
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int N = 1e5+10;
const int LOG = 17;
P edge[N];
vector<P> g[N];
vector<int> ph[N], pp[N];
int par[N][LOG], dep[N];
set<int> s[N];

void dfs(int a = 1, int p = -1) {
	par[a][0] = p;
	rep(i, 1, LOG) {
		int x = par[a][i-1];
		if (x == -1)break;
		par[a][i] = par[x][i-1];
	}
	
	for (auto [i, j]: g[a]) {
		if (i == p)continue;
		dep[i] = dep[a]+1;
		dfs(i, a);
	}
}

int lca(int x, int y) {
	if (dep[y] > dep[x])swap(x, y);
	for (int i = LOG-1; i >= 0; --i) {
		int z = par[x][i];
		//if (i == 1)cout << z << nl;
		if (z != -1 && dep[z] >= dep[y]) {
			//cout << x << " " << " " << z << " " << i << nl;
			x = z;
		}
	}
	
	if (x == y)return x;
	for (int i = LOG-1; i >= 0; --i) {
		int a = par[x][i], b = par[y][i];
		if (a != b)x = a, y = b;
	}
	
	return par[x][0];
}

int cnt[N];
void calc(int a = 1, int p = -1, int idx = -1) {
	for (auto i: ph[a])
		s[a].insert(i);
	for (auto [i, j]: g[a]) {
		if (i == p)continue;
		calc(i, a, j);
		if (sz(s[i]) > sz(s[a]))swap(s[a], s[i]);
		for (auto k: s[i])
			s[a].insert(k);
	}
	for (auto i: pp[a])
		s[a].erase(s[a].find(i));
	if (~idx)cnt[idx] = sz(s[a]);
}

void solve() {
	memset(par, -1, sizeof par);
	int n, m, k; cin >> n >> m >> k;
	rep(i, 0, n-1) {
		int u, v; cin >> u >> v;
		g[u].push_back({v, i});
		g[v].push_back({u, i});
		edge[i] = {u, v};
	}
	
	dfs();
	//cout << par[4][1] << nl;
	//cout << lca(1, 4) << nl;
	rep(i, 0, m) {
		int x, l = -1; cin >> x;
		while (x--) {
			int y; cin >> y;
			ph[y].push_back(i);
			l = (~l?lca(y, l):y);
		}
		//cout << i << " " << l << nl;
		pp[l].push_back(i);
	}
	
	calc();
	vector<int> res;
	rep(i, 0, n-1)
		if (cnt[i] >= k)res.push_back(i+1);
	cout << sz(res) << nl;
	for (auto i: res)cout << i << " ";
	cout << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    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...