wbtree

Wbtree

== include(page="template/taskheader" task_id="wbtree") ==
 

_Cu toţii ştim ce este acela un ciur (adică o sită); putem folosi unul pentru a separa făina grunjoasă de cea fină. Cu toate acestea, în problema de faţă vom încerca să ciuruim nodurile unui arbore._
Nadgob Ciuruitorul are un arbore (graf neorientat conex aciclic) cu $N$ noduri. Nadgob vrea să aleagă o submulţime $S$ de noduri ale arborelui. Pentru a realiza această alegere, el se va aşeza, pe rând, în $K$ noduri *distincte* ale arborelui. Odată aşezat într-un nod $x$ al arborelui, el poate, de oricâte ori doreşte, să selecteze un nod $y$ şi să „ciuruiască” (adică să adauge la $S$) toate nodurile $z$ pentru care $y$ se află pe cel mai scurt drum dintre $x$ şi $z$. Desigur, un nod care este deja în $S$ nu va fi adăugat din nou.

h2. Restricţii

* $1 ≤ K ≤ N ≤ 10^5$
* Pentru ... puncte, $1 ≤ N \times K ≤ 20$
* Pentru alte ... puncte, $1 ≤ N ≤ 20$
* Pentru alte ... puncte, arborele conţine cel mult un nod de grad mai mare de $1$.
* Pentru alte ... puncte, arborele nu conţine niciun nod de grad mai mare de $2$.
* Pentru alte ... puncte, $K = 1$
* Pentru alte ... puncte, $K = N$
* Pentru alte ... puncte, $K = 2$
* Pentru alte ... puncte, $1 ≤ N ≤ 10^3$

* $1 ≤ K ≤ N ≤ 10^5^$
* Pentru 7 puncte, $1 ≤ N * K ≤ 20$
* Pentru alte 9 puncte, $1 ≤ N ≤ 20$
* Pentru alte 9 puncte, arborele conţine cel mult un nod de grad mai mare de $1$.
* Pentru alte 10 puncte, arborele nu conţine niciun nod de grad mai mare de $2$.
* Pentru alte 5 puncte, $K = 1$
* Pentru alte 7 puncte, $K = N$
* Pentru alte 6 puncte, $K = 2$
* Pentru alte 7 puncte, $1 ≤ N ≤ 10^3^$

h2. Exemple

# Selectând $y = 0$, rezultă $S = {0, 1, 2}$.
# Selectând $y = 1$, rezultă $S = {1}$.
# Selectând $y = 2$, rezultă $S = {2}$.

# Selectând $y = 1$ şi $y = 2$, rezultă $S = { 1, 2 }$.

# Selectând $y = 1$ şi $y = 2$, rezultă $S = {1, 2}$.

== include(page="template/taskfooter" task_id="wbtree") ==