Az S. 149. feladat (2021. január)

S. 149. Adott egy \(\displaystyle N\) csúcsból álló fa, csúcsait pozitív egész számokkal jelöljük, gyökere az 1-es csúcs. A fa minden \(\displaystyle P\) csúcsára szeretnénk tudni, hogy hányféleképpen tudunk kiválasztani a fából egy \(\displaystyle K\) darab csúcsból álló rendezett sorozatot úgy, hogy az abban szereplő csúcsok legközelebbi közös őse a \(\displaystyle P\) csúcs legyen. Két kiválasztás különböző, ha abban a választott csúcsok eltérőek, vagy ha a csúcsok sorrendje különböző. A választásban egy csúcs többször is előfordulhat. A \(\displaystyle K\) darab csúcs legközelebbi közös őse az a csúcs, ami őse a \(\displaystyle K\) csúcs mindegyikének, és a lehető legmesszebb van a gyökértől.

Bemenet: az első sor tartalmazza az \(\displaystyle N\) és a \(\displaystyle K\) számot. A következő \(\displaystyle N-1\) sor mindegyike egy \(\displaystyle x\) és \(\displaystyle y\) számot tartalmaz, ami azt jelenti, hogy közöttük fut él.

Kimenet: adjunk meg egy sorban \(\displaystyle N\) darab számot. Az \(\displaystyle i\)-edik szám jelentse a megoldást akkor, ha \(\displaystyle P=i\). A megoldások nagyon nagyok is lehetnek, ezért azok számának modulo \(\displaystyle 10^{9}+7\) maradékát adjuk meg.

Példa:

Magyarázat: nézzük \(\displaystyle P=2\) esetét (\(\displaystyle K=2\), tehát két csúcsot kell sorrendben választani, amelyek legközelebbi közös őse a 2-es csúcs). A lehetséges kiválasztások: 2-2, 2-3, 2-7, 2-4, 2-5, 3-2, 3-4, 3-5, 7-2, 7-4, 7-5, 4-2, 4-3, 4-7, 4-5, 5-2, 5-4, 5-3, 5-7.

Korlátok: \(\displaystyle 3\le N\le {10}^{5}\), \(\displaystyle 2\le K\le {10}^{10}\), \(\displaystyle 0\le xy\le N-1\). Időkorlát: 0,4 mp.

Értékelés: a pontok 30%-a kapható, ha \(\displaystyle K \le 2\).

Beküldendő egy s149.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. február 18-án LEJÁRT.

Egy P pont akkor és csak akkor lehet közös ös, ha a K darab pont P részfájából kerül ki és P benne van a halmazban, vagy legalább két különböző gyerekének részfájában is van kiválasztott pont.

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

HorcsinBalint.pdf

Statisztika:

5 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint.
8 pontot kapott:	1 versenyző.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2021. januári informatika feladatai