Submission #1065145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065145		VectorLi	Railway (BOI17_railway)	C++17	100 / 100	63 ms	23484 KiB

railway

#include <bits/stdc++.h>
#define long long long

using namespace std;

/*
啊哈！
想到结论了就很简单了，按照 DFS 序排序，然后直接做就可以了。
这个结论和 寻宝游戏 使用的结论一样。 
*/

const int N = (int) 1E5;
const int K = 17;

int n;
int p[K][N], d[N];
int t[N], l[N], c;
vector<pair<int, int>> e[N];

void DFS(int u) {
	l[u] = c;
	c = c + 1;
	for (auto [v, i] : e[u]) {
		if (v != p[0][u]) {
			p[0][v] = u;
			d[v] = d[u] + 1;
			t[v] = i;
			DFS(v);
		}
	}
}

int LCA(int u, int v) {
	if (d[u] > d[v]) {
		swap(u, v);
	}
	for (int i = K - 1; i >= 0; i--) {
		if ((d[v] - d[u]) >> i & 1) {
			v = p[i][v];
		}
	}
	if (u == v) {
		return u;
	}
	for (int i = K - 1; i >= 0; i--) {
		if (p[i][u] != p[i][v]) {
			u = p[i][u];
			v = p[i][v];
		}
	}
	return p[0][u];
}

int f[N];

void add(int u, int v) {
	f[u] = f[u] + 1;
	f[v] = f[v] + 1;
	int w = LCA(u, v);
	f[w] = f[w] - 2;
}

bool compare(int u, int v) {
	return l[u] < l[v];
} 

vector<int> answer;

int m, k; 

void DFS2(int u) {
	for (auto [v, i] : e[u]) {
		if (v != p[0][u]) {
			DFS2(v);
			f[u] = f[u] + f[v];
		}
	}
	if (f[u] >= k * 2) {
		answer.push_back(t[u]);
	}
}

void solve() {
	cin >> n >> m >> k;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u = u - 1, v = v - 1;
		e[u].push_back({v, i});
		e[v].push_back({u, i});
	}
	
	p[0][0] = -1;
	DFS(0);
	
	for (int i = 0; i < K - 1; i++) {
		for (int u = 0; u < n; u++) {
			if (p[i][u] >= 0) {
				p[i + 1][u] = p[i][p[i][u]];
			} else {
				p[i + 1][u] = -1;
			}
		}
	}
	
	for (int i = 0; i < m; i++) {
		int N;
		cin >> N;
		vector<int> a(N);
		for (auto& x : a) {
			cin >> x;
			x = x - 1;
		}
		sort(a.begin(), a.end(), compare);
		for (int j = 0; j < N; j++) {
			add(a[j], a[(j + 1) % N]);
		}
	}
	
	DFS2(0);
	sort(answer.begin(), answer.end());
	cout << answer.size() << "\n";
	for (auto x : answer) {
		cout << x + 1 << " ";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	t = 1;
	for (int i = 0; i < t; i++) {
		solve();
	}
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25