Pagini recente » Cod sursa (job #1035042) | Cod sursa (job #2531303)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1005;
int N, K;
int point[NMAX], dist[NMAX];
vector <int> graph[NMAX];
void dfs(int node, int father, const int len)
{
if (graph[node].size() == 1 && node != 1)
{
dist[node] = len + 1;
return;
}
int mx = 0, mn = (1 << 30);
for (auto& i : graph[node])
if (i != father)
{
dfs(i, node, len);
mx = max(mx, dist[i] + 1);
mn = min(mn, dist[i] + 1);
}
dist[node] = mx;
if (mx <= 2 * len)
return;
if (mn <= len && mn + mx - 1 <= 2 * len)
return;
dist[node] = 0;
point[node] = true;
}
int Solve(int len)
{
for (int i = 1;i <= N;++i)
point[i] = dist[i] = 0;
dfs(1, 0, len);
int cnt = 0;
for (int i = 1;i <= N;++i)
cnt += point[i];
return cnt;
}
int main()
{
ifstream fin("salvare.in");
ofstream fout("salvare.out");
fin >> N >> K;
for (int i = 1;i < N;++i)
{
int u, v;
fin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
int left = 1, right = N, mid, answer;
while (left <= right)
{
mid = (left + right) / 2;
if (Solve(mid) <= K)
{
answer = mid;
right = mid - 1;
}
else
left = mid + 1;
}
Solve(answer);
fout << answer << "\n";
for (int i = 1;i <= N;++i)
if (point[i])
fout << i << " ";
fin.close();
fout.close();
return 0;
}