Submission #1297217

#TimeUsernameProblemLanguageResultExecution timeMemory
1297217danirasillaPastiri (COI20_pastiri)C++20
0 / 100
282 ms40072 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) {
	if (alive[nw])
		q.push(nw);
	alive[nw] = false;
	sh[nw] = false;
	
	for (int w : g[nw]) {
		if (alive[w]) {
			if (dis[w] < dis[nw])
				dfs(w, alive, dis, q);
		}
	}
}

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

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