Cod sursa(job #229161)

Utilizator andrei.12Andrei Parvu andrei.12 Data 9 decembrie 2008 16:41:38
Problema Salvare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

#define lg 2000

int n, k, i, x, y, rz[lg], sol[lg], fst[lg], d[lg], jos[lg];
bool pus[lg];
vector<int> v[lg];

void df(int nod){
	int i, pz = 0, f = 0;
	fst[nod] = 1;

	for (i = 0; i < (int)v[nod].size(); i ++)
		if (!fst[v[nod][i]]){
			f = 1;
			df(v[nod][i]);

			//jos[nod] = min(jos[nod], jos[v[nod][i]]);
			if (jos[v[nod][i]] < jos[nod])
				jos[nod] = jos[v[nod][i]], pz = v[nod][i];
		}
	if (!f)
		d[nod] = 0;
	jos[nod] ++;

	for (i = 0; i < (int)v[nod].size(); i ++)
		if (fst[v[nod][i]] == 2)
			if (d[v[nod][i]] + 1 + jos[nod] > x || v[nod][i] == pz){
				d[nod] = max(d[nod], d[v[nod][i]] + 1);

				if (nod == 1 && d[v[nod][i]] >= 0){
					rz[++ rz[0]] = nod, d[1] = 0, pus[nod] = 1;
					break;
				}
			}

	if (d[nod] == x /*&& nod != 1*/)
		d[nod] = -x-1, jos[nod] = 0, rz[++ rz[0]] = nod, pus[nod] = 1;

	fst[nod] = 2;
}
int ok(){
	memset(fst, 0, sizeof(fst));
	memset(jos, 0x3f, sizeof(jos));
	memset(pus, 0, sizeof(pus));
	memset(d, -0x3f, sizeof(d));
	memset(rz, 0, sizeof(rz));

	df(1);

	if (rz[0] <= k){
		int ii = k - rz[0];

		for (int i = 1; ii; i ++)
			if (!pus[i])
				rz[++ rz[0]] = i, ii --;
		return 1;
	}
	return 0;
}

int main()
{
	freopen("salvare.in", "rt", stdin);
	freopen("salvare.out", "wt", stdout);

	scanf("%d%d", &n, &k);
	for (i = 1; i < n; i ++){
		scanf("%d%d", &x, &y);

		v[x].push_back(y); v[y].push_back(x);
	}

	int li = 0, ls = n, gs = -1;

	while (li <= ls){
		x = (li + ls) / 2;

		if (ok()){
			gs = x;
			memcpy(sol, rz, sizeof(sol));
			ls = x-1;
		}
		else
			li = x+1;
	}

	printf("%d\n", gs);

	sort(sol + 1, sol + sol[0] + 1);

	for (i = 1; i <= sol[0]; i ++)
		printf("%d ", sol[i]);
	printf("\n");

	return 0;
}