Cod sursa(job #55422)

Utilizator dominoMircea 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;
}