This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC target ("avx2")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int) (x).size())
#define pb push_back
#define mp make_pair
//#define int long long
using namespace std;
using namespace __gnu_pbds;
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;
const ll base = 1e6 + 9;
const ll inf = 1e9;
const int MAX = 5e5 + 15;
const int LG = 19;
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);
int n;
int timer = 0;
int tin[MAX], tout[MAX], d[MAX];
int up[MAX][LG];
vector<int> g[MAX];
void dfs(int v, int p = 0) {
tin[v] = timer++;
up[v][0] = p;
for(auto to : g[v]) {
if(to == p) continue;
d[to] = d[v] + 1;
dfs(to, v);
}
tout[v] = timer;
}
bool anc(int u, int v) {
return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int LCA(int u, int v) {
if(anc(u, v)) return u;
if(anc(v, u)) return v;
for(int l = LG - 1; ~l; l--) {
if(!anc(up[u][l], v)) u = up[u][l];
}
return up[u][0];
}
int dist(int u, int v) {
return d[u] + d[v] - 2 * d[LCA(u, v)];
}
vector<int> bfs(int s) {
vector<int> d(n + 1, inf);
queue<int> q;
q.push(s);
d[s] = 0;
while(sz(q)) {
int v = q.front(); q.pop();
for(auto to : g[v]) {
if(d[to] > d[v] + 1) {
d[to] = d[v] + 1;
q.push(to);
}
}
}
return d;
}
void solve() {
int k;
cin >> n >> k;
for(int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
vector<int> a(k);
for(auto &i : a) {
cin >> i;
}
dfs(1);
vector<vector<int>> d(n + 1, vector<int>(k));
for(int i = 0; i < k; i++) {
auto dist = bfs(a[i]);
for(int v = 1; v <= n; v++) {
d[v][i] = dist[v];
}
}
vector<pair<int, int>> cnt;
for(int v = 1; v <= n; v++) {
int c = 0;
int mn = *min_element(all(d[v]));
for(int i = 0; i < k; i++) c += (d[v][i] == mn);
cnt.pb({c, v});
}
sort(all(cnt));
vector<int> ans;
vector<int> used(k);
int left = k;
while(left) {
auto [c, v] = cnt.back(); cnt.pop_back();
int mn = *min_element(all(d[v]));
for(int i = 0; i < k; i++) {
if(d[v][i] == mn) {
if(!used[i]) left--;
used[i] = 1;
}
}
ans.pb(v);
}
sort(all(ans));
cout << sz(ans) << '\n';
for(auto v : ans) cout << v << " ";
}
signed main() {
tout[0] = inf;
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int ttt = 1;
// cin >> ttt;
while(ttt--) solve();
}
# | 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... |