Pagini recente » Cod sursa (job #100830) | Cod sursa (job #2817067) | Cod sursa (job #2895238) | Cod sursa (job #3289330) | Cod sursa (job #2351156)
#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], DPBound;
bool Flag[MAXN];
void DFS(int Vertex = 1, int Parent = 0) {
int Sum = 0;
for (auto Edge:ADC[Vertex])
if (Edge != Parent)
DFS(Edge, Vertex), Sum += DP[Edge] + 1;
if (Parent) Sum++;
if (Sum > DPBound)
++ SavePoints, Flag[Vertex] = 1, Sum = 0;
DP[Vertex] = Sum;
}
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';
DPBound = Ans;
for (int i=1; i<=N; ++i)
if (Flag[i])
Out << i << ' ';
}
int main()
{
Citire();
Rezolvare();
return 0;
}