#include <bits/stdc++.h>
using namespace std;
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define db(...) " [" << #__VA_ARGS__ << " : " << (__VA_ARGS__) << "] "
#define BIT(x, i) ((x) >> (i) & 1)
#define MASK(x) (1LL << (x))
#define N 500005
int n, k;
int x[N];
int h[N];
int sz[N];
int par[N];
int head[N];
vector<int> g[N];
void dfs(int u = 1) {
sz[u] = 1;
for (int v : g[u]) {
if (v != par[u]) {
par[v] = u;
h[v] = h[u] + 1;
dfs(v);
sz[u] += sz[v];
}
}
for (int &v : g[u]) {
if (v == par[u]) {
swap(v, g[u].back());
g[u].pop_back();
break;
}
}
}
void hld(int u = 1, int h = 1) {
head[u] = h;
if (g[u].size()) {
int x = *max_element(g[u].begin(), g[u].end(), [&](int i, int j) {
return sz[i] < sz[j];
});
hld(x, h);
for (int v : g[u]) {
if (v != x) {
hld(v, v);
}
}
}
}
int lca(int u, int v) {
while (head[u] != head[v]) {
if (sz[head[u]] > sz[head[v]]) {
swap(u, v);
}
u = par[head[u]];
}
return sz[u] < sz[v] ? v : u;
}
int dist(int u, int v) {
return h[u] + h[v] - 2 * h[lca(u, v)];
}
template<class A, class B>
bool mini(A &a, const B &b) {
return a > b ? (a = b), true : false;
}
namespace sub1 {
bool valid_input() {
bool test = true;
for (int i = 1; i <= n; ++i) {
for (int j : g[i]) {
test &= (abs(j - i) == 1);
}
}
return test;
}
int dp[2][N];
int child[2][N];
pair<int, int> par[2][N];
bool mid(int l, int r) {
return (l > 0 && (r - l) % 2 == 0);
}
void solve() {
sort(x + 1, x + k + 1);
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = dp[1][0] = 0;
for (int i = 1; i <= k; ++i) {
// case 1: dat 1 con phu i va i - 1 (neu x[i] - x[i - 1] & 1)
if (mid(x[i - 1], x[i])) {
if (mini(dp[1][i], dp[0][i - 1] + 1)) {
child[1][i] = x[i - 1] + (x[i] - x[i - 1]) / 2;
par[1][i] = {0, i - 1};
}
}
// case 2: dat tai i
if (mini(dp[1][i], dp[1][i - 1] + 1)) {
child[1][i] = x[i];
par[1][i] = {1, i - 1};
}
// case 3: k dat tai i
dp[0][i] = dp[1][i - 1];
par[0][i] = {1, i - 1};
}
int t = 1;
vector<int> res;
do {
if (child[t][k]) {
res.emplace_back(child[t][k]);
}
pair<int, int> prv = par[t][k];
t = prv.first;
k = prv.second;
} while (k != 0);
cout << res.size() << "\n";
for (int idx : res) {
cout << idx << " ";
}
exit(0);
}
}
namespace sub2 {
bool valid_input() {
return k <= 15;
}
int g[MASK(15)];
int child[MASK(15)];
pair<int, int> prv[MASK(15)];
vector<int> res;
void dfs(int u) {
if (g[u] <= 1) {
if (child[u]) {
res.emplace_back(child[u]);
}
return;
}
dfs(prv[u].first);
dfs(prv[u].second);
}
void solve() {
memset(g, 0x3f, sizeof(g));
g[0] = 0;
for (int i = 1; i <= n; ++i) {
int mn = n + 1, mask = 0;
for (int j = 1; j <= k; ++j) {
int dis = dist(i, x[j]);
if (mn > dis) {
mn = dis;
mask = MASK(j - 1);
} else if (mn == dis) {
mask |= MASK(j - 1);
}
}
if (mini(g[mask], 1)) {
child[mask] = i;
}
}
for (int mask = 0; mask < MASK(k); ++mask) {
for (int smask = mask; smask; smask = (smask - 1) & mask) {
if (mini(g[smask], g[mask])) {
child[smask] = child[mask];
}
}
}
for (int mask = 0; mask < MASK(k); ++mask) {
for (int smask = mask; smask; smask = (smask - 1) & mask) {
if (mini(g[mask], g[smask] + g[mask ^ smask])) {
prv[mask] = {smask, mask ^ smask};
}
}
}
dfs(MASK(k) - 1);
cout << res.size() << "\n";
for (int idx : res) {
cout << idx << " ";
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
file("SHEEP");
cin >> n >> k;
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
dfs();
hld();
for (int i = 1; i <= k; ++i) {
cin >> x[i];
}
if (sub1::valid_input()) {
sub1::solve();
}
if (sub2::valid_input()) {
sub2::solve();
}
}
Compilation message
pastiri.cpp: In function 'int main()':
pastiri.cpp:5:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:197:3: note: in expansion of macro 'file'
197 | file("SHEEP");
| ^~~~
pastiri.cpp:5:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
5 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
pastiri.cpp:197:3: note: in expansion of macro 'file'
197 | file("SHEEP");
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
94544 KB |
Output is correct |
| 2 |
Correct |
139 ms |
94672 KB |
Output is correct |
| 3 |
Correct |
148 ms |
94696 KB |
Output is correct |
| 4 |
Correct |
197 ms |
103392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
21332 KB |
Output is correct |
| 2 |
Correct |
16 ms |
21336 KB |
Output is correct |
| 3 |
Execution timed out |
1034 ms |
47184 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
18940 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
375 ms |
46248 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
