Pagini recente » Cod sursa (job #2852685) | Cod sursa (job #1570031) | Cod sursa (job #1215424) | Gruparea testelor | Cod sursa (job #2351164)
#include <bits/stdc++.h>
#define MAXN 1005
int N, K;
std::vector <int> ADC[MAXN];
inline void AddEdge(int X, int Y) {
ADC[X].push_back(Y);
ADC[Y].push_back(X);
}
int SavePoints, Ans;
int DP[MAXN], Count[MAXN], DPBound;
bool Flag[MAXN];
void DFS(int Vertex = 1, int Parent = 0) {
for (auto Edge:ADC[Vertex])
if (Edge != Parent)
DFS(Edge, Vertex);
DP[Vertex] = MAXN;
Count[Vertex] = DPBound;
for (auto Edge:ADC[Vertex])
if (Edge != Parent)
DP[Vertex] = std::min(DP[Vertex], DP[Edge] + 1),
Count[Vertex] = std::min(Count[Vertex], Count[Edge] - 1);
if (DP[Vertex] <= Count[Vertex])
Count[Vertex] = MAXN;
if (!Count[Vertex])
++SavePoints, Flag[Vertex] = 1,
Count[Vertex] = MAXN, DP[Vertex] = 0;
}
std::ifstream In ("salvare.in");
std::ofstream Out("salvare.out");
bool Check(int Bound) {
SavePoints = 0;
DPBound = Bound;
for (int i=1; i<=N; ++i)
DP[i] = Flag[i] = 0;
DFS();
return (SavePoints <= K);
}
void Citire() {
In >> N >> K;
for (int i=1, X, Y; i<N; ++i)
In >> X >> Y, AddEdge(X, Y);
}
void Rezolvare() {
int lbound = 1, rbound = N, mid;
while (lbound <= rbound) {
mid = (lbound + rbound)/2;
if (Check(mid))
Ans = mid, rbound = mid-1;
else
lbound = mid+1;
} Out << Ans << '\n';
Check(Ans);
for (int i=1; i<=N; ++i)
if (Flag[i])
Out << i << ' ';
}
int main()
{
Citire();
Rezolvare();
return 0;
}