제출 #697413

#제출 시각아이디문제언어결과실행 시간메모리
697413d4xnRailway (BOI17_railway)C++17
0 / 100
106 ms25432 KiB
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, L = 20;

int n, m, k, tim, dep[N], sz[N], pre[N], upId[N], f[N], up[L][N];
vector<pair<int, int>> adj[N];

void dfs(int u, int par, int id, int d) {
	dep[u] = d;
	pre[u] = tim++;
	sz[u] = 1;
	upId[u] = id;
	for (auto &[v, idx] : adj[u]) {
		if (v == par) continue;
		up[0][v] = u;
		dfs(v, u, idx, d + 1);
		sz[u] += sz[v];
	}
}

int lca(int x, int y) {
	if (dep[x] < dep[y])
		swap(x, y);
	int dif = dep[x] - dep[y];
	for (int b = 0; b < L; b++) {
		if (dif & (1 << b))
			x = up[b][x];
	}
	if (x == y)
		return x;

	for (int b = L - 1; b >= 0; b--) {
		if (up[b][x] == up[b][y])
			continue;
		x = up[b][x];
		y = up[b][y];
	}
	return up[0][x];
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m >> k;
	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		adj[x].push_back(make_pair(y, i));
		adj[y].push_back(make_pair(x, i));
	}
	tim = 0;
	dfs(0, 0, -1, 0);

	for (int j = 1; j < L; j++) {
		for (int i = 0; i < n; i++) {
			up[j][i] = up[j - 1][up[j - 1][i]];
		}
	}

	while (m--) {
		int x;
		cin >> x;
		vector<int> tims(x);
		vector<pair<int, int>> ordP(x), ordD(x);
		for (int i = 0; i < x; i++) {
			int y;
			cin >> y;
			y--;
			tims[i] = pre[y];
			ordP[i] = make_pair(pre[y], y);
			ordD[i] = make_pair(dep[y], y);
		}
		sort(tims.begin(), tims.end());
		sort(ordP.begin(), ordP.end());
		sort(ordD.rbegin(), ordD.rend());

		for (int i = 0; i < x; i++) {
			int y = ordD[i].second;
			f[y]++;
			int l = upper_bound(tims.begin(), tims.end(), pre[y]) - tims.begin();
			int r = lower_bound(tims.begin(), tims.end(), pre[y]+sz[y]) - tims.begin();
			f[y] -= r-l;
		}

		int l = ordP[0].second;
		int r = ordP.back().second;
		f[lca(l, r)]--;
	}

	vector<pair<int, int>> ordD(n);
	for (int i = 0; i < n; i++) {
		ordD[i] = make_pair(dep[i], i);
	}
	sort(ordD.rbegin(), ordD.rend());

  vector<int> ans;
  for (int i = 0; i < n; i++) {
    int x = ordD[i].second;
    if (f[x] >= k) ans.push_back(upId[x]);
    f[up[0][x]] += f[x];
  }
  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...