Submission #1297256

#TimeUsernameProblemLanguageResultExecution timeMemory
1297256danirasillaPastiri (COI20_pastiri)C++20
100 / 100
293 ms86756 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];

pair<int, int> dfs(int nw, int pr, vector<int>& dis, vector<int>& res) {
	int up = -1;
	int down = -1;
	if (sh[nw])
		down = 0;
	for (int w : g[nw]) {
		if (w == pr)
			continue;
		auto ww = dfs(w, nw, dis, res);
		if (ww.first != -1) {
			down = max(down, ww.first + 1);
		}
		else
			up = max(up, ww.second - 1);
	}
	if (up >= down || down == -1)
		return { -1, up };
	if ((pr == -1 || dis[nw] >= dis[pr]) && down != -1) {
		res.push_back(nw);
		return { -1, dis[nw]};
	}
	return { down, -1 };
}

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;
		for (int i = 0; i < n; i++)
			st[i] = g[i].size();
			
		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 (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 (dis[w] > dis[i])
					sp[i] = false;
		vector<int> res;
		dfs(0, -1, dis, res);
		cout << res.size() << "\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...