Feladat: S.149 Korcsoport: 18- Nehézségi fok: nehéz
Füzet: 2021/január, 38. oldal  PDF  |  MathML 

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Adott egy 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 P csúcsára szeretnénk tudni, hogy hányféleképpen tudunk kiválasztani a fából egy K darab csúcsból álló rendezett sorozatot úgy, hogy az abban szereplő csúcsok legközelebbi közös őse a 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 K darab csúcs legközelebbi közös őse az a csúcs, ami őse a K csúcs mindegyikének, és a lehető legmesszebb van a gyökértől.
Bemenet: az első sor tartalmazza az N és a K számot. A következő N-1 sor mindegyike egy x és y számot tartalmaz, ami azt jelenti, hogy közöttük fut él.
Kimenet: adjunk meg egy sorban N darab számot. Az i-edik szám jelentse a megoldást akkor, ha P=i. A megoldások nagyon nagyok is lehetnek, ezért azok számának modulo 109+7 maradékát adjuk meg.
Példa:

 
Bemenet  (a  /  jel sortörést helyettesít)Kimenet   7 2 / 1 2 / 1 6 / 2 3 / 2 4 / 2 5 / 3 723 19 3 1 1 1 1   
 

Magyarázat: nézzük P=2 esetét (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: 3≤N≤105, 2≤K≤1010, 0≤xy≤N-1. Időkorlát: 0,4 mp.
Értékelés: a pontok 30%-a kapható, ha K≤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ó.