#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 500101
#define MAXS 25
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<int> adj[MAX];
int dis[MAX];
int sheep[MAX];
vector<int> v;
int vis[MAX];
int dep[MAX];
int prt[MAX];
int sp[MAX][MAXS];
int N, K;
namespace centroid {
int cp[MAX];
int cd[MAX];
int num[MAX];
int vis[MAX];
int mx[MAX];
int dis[MAXS][MAX];
void make_num(int x, int p = 0) {
num[x] = 1;
for (auto v : adj[x]) if (v != p) {
if (vis[v]) continue;
make_num(v, x);
num[x] += num[v];
}
}
void make_dis(int x, int c, int p = 0) {
for (auto v : adj[x]) {
if (vis[v]) continue;
if (v == p) continue;
dis[c][v] = dis[c][x] + 1;
make_dis(v, c, x);
}
}
void make_tree(int x, int p = 0, int d = 0) {
make_num(x);
int c = x;
int n = num[x];
while (1) {
bool changed = false;
for (auto v : adj[c]) {
if (num[v] > num[c]) continue;
if (vis[v]) continue;
if (num[v] > n / 2) {
c = v;
changed = true;
break;
}
}
if (!changed) break;
}
make_dis(c, d);
vis[c] = 1;
cp[c] = p;
cd[c] = d;
for (auto v : adj[c]) {
if (vis[v]) continue;
make_tree(v, c, d + 1);
}
}
inline void upd(int i, int d) {
int v = i;
while (v) {
mx[v] = max(mx[v], d - dis[cd[v]][i]);
v = cp[v];
}
}
inline int chk(int i) {
int v = i;
while (v) {
if (dis[cd[v]][i] <= mx[v]) return true;
v = cp[v];
}
return false;
}
void init() {
make_tree(1);
for (int i = 1; i <= N; i++) mx[i] = -1;
}
}
void dfs(int x, int p = 0) {
if (sheep[x]) dis[x] = 0;
else dis[x] = 10101010;
prt[x] = p;
sp[x][0] = p;
int i;
for (i = 1; i < MAXS; i++) sp[x][i] = sp[sp[x][i - 1]][i - 1];
for (auto v : adj[x]) {
if (v == p) continue;
dep[v] = dep[x] + 1;
dfs(v, x);
dis[x] = min(dis[x], dis[v] + 1);
}
}
void down(int x, int p = 0) {
for (auto v : adj[x]) if (v != p) {
dis[v] = min(dis[v], dis[x] + 1);
down(v, x);
}
}
void chk(int x, int d, int p = 0) {
sheep[x] = 0;
if (!d) return;
for (auto v : adj[x]) if (v != p) chk(v, d - 1, x);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> K;
int i, a, b;
for (i = 1; i < N; i++) {
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<int> sv;
for (i = 1; i <= K; i++) {
cin >> a;
sv.push_back(a);
sheep[a] = 1;
}
dfs(1);
down(1);
sort(sv.begin(), sv.end(), [&](int a, int b) {return dep[a] > dep[b]; });
int cnt = 0;
vector<int> ans;
centroid::init();
for (auto x : sv) {
if (centroid::chk(x)) continue;
cnt++;
int v = x;
for (i = MAXS - 1; i >= 0; i--) {
int p = sp[v][i];
if (!p) continue;
if (dis[p] >= dep[x] - dep[p]) v = p;
}
ans.push_back(v);
centroid::upd(v, dis[v]);
}
cout << ans.size() << ln;
for (auto v : ans) cout << v << bb;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
371 ms |
181108 KB |
Output is correct |
| 2 |
Correct |
377 ms |
182620 KB |
Output is correct |
| 3 |
Correct |
374 ms |
182628 KB |
Output is correct |
| 4 |
Correct |
507 ms |
189692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
13232 KB |
Output is correct |
| 2 |
Correct |
9 ms |
13268 KB |
Output is correct |
| 3 |
Execution timed out |
1061 ms |
122412 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12628 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12676 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12532 KB |
Output is correct |
| 4 |
Correct |
6 ms |
12468 KB |
Output is correct |
| 5 |
Correct |
8 ms |
12596 KB |
Output is correct |
| 6 |
Correct |
7 ms |
12604 KB |
Output is correct |
| 7 |
Correct |
7 ms |
12628 KB |
Output is correct |
| 8 |
Correct |
7 ms |
12600 KB |
Output is correct |
| 9 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 10 |
Correct |
6 ms |
12476 KB |
Output is correct |
| 11 |
Correct |
7 ms |
12372 KB |
Output is correct |
| 12 |
Correct |
6 ms |
12372 KB |
Output is correct |
| 13 |
Correct |
7 ms |
12472 KB |
Output is correct |
| 14 |
Correct |
7 ms |
12728 KB |
Output is correct |
| 15 |
Correct |
7 ms |
12628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1069 ms |
133648 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
