Pagini recente » Cod sursa (job #628076) | Cod sursa (job #117814) | Cod sursa (job #2973889) | Cod sursa (job #1171946) | Cod sursa (job #1486031)
#include<fstream>
#include<cstring>
#include<algorithm>
#define Nmax 1024
#define mp make_pair
using namespace std;
ifstream f("salvare.in"); ofstream g("salvare.out");
int N,K,nv,a[Nmax][Nmax],deg[Nmax],up[Nmax];
pair <int, int> V[Nmax];
char U[Nmax],sol[Nmax];
void DFS(int n, int lev)
{ V[nv++]=mp(lev,n);
for(int *p=a[n];*p;p++)
if(*p!=up[n]) {up[*p]=n; DFS(*p,lev-1);}
}
void DFS2(int n, int up, int d)
{ U[n]=1;
if(d==0) return;
for(int *p=a[n];*p;p++)
if(*p!=up) DFS2(*p,n,d-1);
}
int works(int D)
{ memset(U,0,sizeof(U));
memset(sol,0,sizeof(sol));
int ret=0;
for(int i=0;i<nv;i++)
{ int j=V[i].second;
if(U[j]) continue;
for(int d=D;up[j] && d;j=up[j],d--);
sol[j]=1; ret++;
DFS2(j,0,D);
}
return ret;
}
int main()
{ int i,j,r;
f>>N>>K;
for(r=1;r<N;r++)
{f>>i>>j; a[i][deg[i]++]=j; a[j][deg[j]++]=i;}
DFS(1,0);
sort(V,V+nv);
for(r=1;r<N;r<<=1);
for(i=N;r;r>>=1)
if(i-r>=0 && works(i-r)<= K) i-=r;
K-=works(i);
for(j=1;j<=N && K;j++)
if(!sol[j]){sol[j]=1; K--;}
g<<i<<'\n';
for(j=1;j<=N;j++) if(sol[j]) g<<j<<' ';
g<<'\n'; g.close(); return 0;
}