#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 time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |