Cod sursa(job #1982887)

Utilizator lflorin29Florin Laiu lflorin29 Data 20 mai 2017 15:20:30
Problema Salvare Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <bits/stdc++.h>
#define Maxn 1003
using namespace std;

int n, k, tmax, v[Maxn];
vector<int>g[Maxn];
vector<int>centre, fn;

void read() {
	scanf("%d%d", &n, &k);

	for (int i = 1; i < n; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
}

void dfs(int nod, int tata) {
	for (auto i : g[nod]) {
		if (i != tata) {
			dfs(i, nod);
			v[nod] = max(v[nod], v[i] + 1);
		}
	}

	if (v[nod] == tmax) {
		centre.push_back(nod);
		v[nod] = 0;
	}
}

void solve() {
	int st = 0, dr = n-1 , rez = 0;

	while (st <= dr) {
		int mid = (st + dr) / 2;
		centre.clear();
		memset(v, 0 , sizeof v);
		tmax = mid;
		dfs(1, 0);

		if (centre.size() <= k) {
			rez = mid;
			dr = mid - 1;
			fn = centre;
		}
		else st = mid + 1;
	}

	printf("%d\n", rez);
	vector<bool>T(n + 1);

	for (auto i : fn) T[i] = 1;

	for (int i = 1; i <= n; ++i)
		if (!T[i])fn.push_back(i), T[i] = 1;

	sort(fn.begin(), fn.end());

	for (auto i : fn)
		printf("%d ", i);
}
int main() {
	freopen("salvare.in", "r", stdin);
	freopen("salvare.out", "w", stdout);

	read();
	solve();
}