Submission #1295590

#TimeUsernameProblemLanguageResultExecution timeMemory
1295590danirasillaPastiri (COI20_pastiri)C++20
0 / 100
1117 ms552092 KiB
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <iterator>
#include <set>
#include <random>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <stack>
#include <numeric>
#include <deque>


using namespace std;
typedef long long ll;
typedef long double ld;
const ll md1 = 1'000'000'000;
const ll md2 = 998244353;
const ll mdd = 666013;
int n, k;
const int N = 500'001;
vector<int> g[N];
bool sh[N];

void dfs(int nw, vector<bool>& alive, vector<int>& dis, queue<int>& q, vector<int>& st, vector<bool>& sp) {
	alive[nw] = false;
	q.push(nw);
	sh[nw] = false;
	for (int w : g[nw]) {
		if (alive[w]) {
			if (dis[w] < dis[nw])
				dfs(w, alive, dis, q, st, sp);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
	//cin >> t;
	while (t--) {

		cin >> n >> k;
		vector<pair<int, int>> e(n - 1);
		for (int i = 1; i < n; i++) {
			int v, u;
			cin >> v >> u;
			v--, u--;
			e[i - 1] = { v, u };
			g[v].push_back(u);
			g[u].push_back(v);
		}
		for (int i = 0; i < k; i++) {
			int v;
			cin >> v;
			sh[v - 1] = true;
		}
		vector<int> st(n);
		queue<int> q;
		vector<bool> alive(n, true);
		for (int i = 0; i < n; i++) {
			st[i] = g[i].size();
			if (st[i] == 1 && !sh[i]) {
				q.push(i);
				alive[i] = false;
			}
		}
		while (!q.empty()) {
			int nw = q.front();
			q.pop();
			for (int w : g[nw]) {
				st[w]--;
				if (alive[w] && !sh[w] && st[w] == 1) {
					q.push(w);
					alive[w] = false;
				}
			}
		}
		vector<int> dis(n, -1);
		for (int i = 0; i < n; i++) {
			if (sh[i]) {
				q.push(i);
				dis[i] = 0;
			}
		}
		while (!q.empty()) {
			int nw = q.front();
			q.pop();
			for (int w : g[nw]) {
				if (alive[w] && dis[w] == -1) {
					dis[w] = dis[nw] + 1;
					q.push(w);
				}
			}
		}
		vector<bool> sp(n, true);
		for (int i = 0; i < n; i++)
			for (int w : g[i])
				if (alive[w] && dis[w] > dis[i])
					sp[i] = false;

		for (int i = 0; i < n; i++)
			if (st[i] <= 1 && alive[i]) {
				q.push(i);
				alive[i] = false;
			}
		int ans = 0;
		vector<int> res;
		while (!q.empty()) {
			int nw = q.front();
			q.pop();

			if (sp[nw]) {
				ans++;
				res.push_back(nw);
				dfs(nw, alive, dis, q, st, sp);
			}
			else {
				if (sh[nw]) {
					for (int w : g[nw]) {
						st[w]--;
						sh[w] = true;
						if (alive[w] && (st[w] <= 1 || sp[w])) {
							q.push(w);
							alive[w] = false;
						}

					}
				}
				else {
					for (int w : g[nw]) {
						st[w]--;
						if (alive[w] && st[w] <= 1 && !(sp[w] && !sh[w])) {
							q.push(w);
							alive[w] = false;
						}

					}
				}
			}

		}
		cout << ans << "\n";
		sort(res.begin(), res.end());
		for (int w : res)
			cout << w + 1 << " ";
		cout << "\n";
	}
	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...