Az S. 148. feladat (2020. december)

S. 148. Adott egy $\displaystyle N$ csúcsú fa. Megkértek minket, hogy töröljük ennek a fának az egyik levelét, tehát egy olyan csúcsot, aminek pontosan egy éle van. Jelöljük ezt a levelet $\displaystyle L$-lel. A törlés után visszamarad egy $\displaystyle N-1$ csúcsú fa. Ebben az új fában jelöljük $\displaystyle D$-vel két, egymástól legmesszebb levő pont távolságát, és $\displaystyle P$-vel azon (nem rendezett) pontpárok számát, amelyek távolsága $\displaystyle D$. Adjuk meg $\displaystyle P$ minimális értékét és azt, hogy ehhez hányféleképpen választhatjuk meg az $\displaystyle L$ levelet (amit törlünk).

Bemenet: az első sor tartalmazza az $\displaystyle N$ számot. A csúcsokat 0-tól indexeljük. A következő $\displaystyle N-1$ sor mindegyike egy $\displaystyle x$ és egy $\displaystyle y$ számot tartalmaz, ami azt jelenti, hogy az $\displaystyle x$-edik és $\displaystyle y$-adik csúcsot él köti össze.

Kimenet: adjuk meg $\displaystyle P$ minimális értéket, és azt, hogy az hányféleképpen érhető el.

Példa:

Magyarázat: ha töröljük a 0-s csúcsot, akkor $\displaystyle D=4$, és a 2-es és 6-os csúcsok távolsága 4, tehát $\displaystyle P = 1$. Ha töröljük a 2-es csúcsot, akkor $\displaystyle D=4$, és a 0-s és 6-os csúcsok távolsága 4, tehát $\displaystyle P = 1$. Két esetben kaptunk minimális $\displaystyle P=1$-et, a többi esetben $\displaystyle P$ nagyobb lesz.

Korlátok: $\displaystyle 3\le N\le {10}^{5}$, $\displaystyle 0\le x,y\le N-1$. Időkorlát: 0,3 mp.

Értékelés: a pontok 50%-a kapható, ha $\displaystyle N \le 100$.

Beküldendő egy s148.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2021. január 15-én LEJÁRT.

Két fő esetünk van:

Ha eltávolítunk egy adott pontot, akkor a fa leghosszabb útjának hossza nem változik, vagy változik.

Mindkét esetet figyelembe kell venni, hogy optimálisan válasszunk.

Részletes leírás ábrával az egyedüli maxpontos Horcsin Bálint megoldásában:

HorcsinBalint.pdf

Statisztika:

4 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint.
9 pontot kapott:	Varga 256 Péter.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.

A KöMaL 2020. decemberi informatika feladatai