Pagini recente » Cod sursa (job #2129229) | Cod sursa (job #2094853) | Cod sursa (job #681869) | Cod sursa (job #2197698) | Cod sursa (job #55422)
Cod sursa(job #55422)
Utilizator |
Mircea Pasoi domino |
Data |
27 aprilie 2007 13:42:41 |
Problema |
Salvare |
Scor |
Ascuns |
Compilator |
cpp |
Status |
done |
Runda |
|
Marime |
2.08 kb |
#include<stdio.h>
#include<vector>
#include<algorithm>
#define pb push_back
#define vi vector <int>
#define vii vector <int> :: iterator
const int maxn = 1001;
using namespace std;
int n;
int x;
int y;
int i;
int p;
vi ans;
int ver[maxn];
const int inf = 1000000;
vi vect[maxn];
int maxi[maxn];
int k;
int num;
int l;
int max(int i,int j)
{
return i < j ? j : i;
}
void dfs(int i,int pr)
{
vii it;
for(it = vect[i].begin();it != vect[i].end(); ++it)
{
if (!ver[*it])
{
ver[*it] = 1;
dfs(*it,pr);
}
}
int max1 = -inf;
for(it = vect[i].begin();it != vect[i].end(); ++it)
{
maxi[i] = max(maxi[i],maxi[*it] + 1);
}
int last = 0;
for(it = vect[i].begin();it != vect[i].end(); ++it)
{
if (max1 < maxi[*it] + 1)
{
last = *it;
max1 = maxi[*it] + 1;
}
}
int max2 = -inf;
for(it = vect[i].begin();it != vect[i].end(); ++it)
{
if (*it == last) continue;
if (max2 < maxi[*it] + 1)
{
max2 = maxi[*it] + 1;
}
}
if (max1 + max2 > l)
{
num++;
maxi[i] = 0;
if (pr) ans.pb(i);
}
}
bool veri(int x)
{
num = 0;
l = x;
dfs(1,0);
for(i = 1;i <= n; ++i)
{
ver[i] = 0;
maxi[i] = 0;
}
ver[1] = 1;
return num <= k;
}
int main()
{
freopen("salvare.in","r",stdin);
freopen("salvare.out","w",stdout);
scanf("%d %d",&n,&k);
// printf("%d %d",n,k);
for(i = 1;i <= n - 1; ++i)
{
scanf("%d %d",&x,&y);
vect[x].pb(y);
vect[y].pb(x);
}
for(p = 1;p <= n; p <<= 1);
x = 0;
ver[1] = 1;
for(;p;p >>= 1)
{
if (!veri(x + p))
{
x += p;
}
}
x++;
dfs(1,1);
printf("%d\n",x);
sort(ans.begin(),ans.end());
int i;
int n = ans.size();
for(i = 0;i < n; ++i)
{
printf("%d ",ans[i]);
}
printf("\n");
return 0;
}