Գորիլա

Պարոն Գորիլան սիրում է տարբեր տեսակի մրգեր ուտել։ Նա գտել է մի տարորինակ ծառ, որի վրա աճում են տարբեր տեսակի մրգեր։ Այդ ծառը կարելի է ներկայացնել գագաթ և կող ունեցող կապակցված գրաֆի միջոցով, որի գագաթները համարակալված են -ից թվերով։ Ընդ որում համարով գագաթը համապատասխանում է ծառի արմատին։

Կա մրգերի տեսակ, որոնք համարակալված են -ից թվերով։ Այնպես է ստացվել, որ յուրաքանչյուր ճյուղի (կողի) վրա աճում են իրար հետևից եկող համարներ ունեցող տեսակների մրգեր։

Ավելի կոնկրետ -րդ կողը միացնում է և գագաթները և դրա վրա աճում են -ից տեսակների մրգերը։

Գորիլան ցանկանում է ընտրել որոշակի գագաթ և մագլցել արմատից միչև այդ գագաթը ուտելով ճանապահին հանդիպած բոլոր մրգերը։ Սակայն նա դժվարանում է ընտրություն կայացնել, այդ իսկ պաճառով ուզում է իմանալ մրգերի տարբեր տեսակների քանակը, որոնցից նա կկարողանա համտեսել, բոլոր արմատ չհանդիսացող գագաթներ մագլցելու դեպքում (իրարից անկախ)։

Մուտքային տվյալներ

Առաջին տողում տրված են երկու բնական թվեր՝ և . ծառի գագաթների և մրգերի տեսակների քանակները։ Հաջորդ տողերից յուրաքանչյուրում տրված է քառյակ ․ որը ցույց է տալիս, որ i-րդ կողը (ճյուղը) միացնում է և համարներով գագաթները , և այդ կողով անցնելիս Գորիլան ուտում է միջակայքի բոլոր տեակների մրգերը ։ Երաշխավորվում է որ տրված գրաֆը կապակցված է։

Ելքային տվյալներ

Պետք է արտածել հատ թիվ, որտեղ -րդ թիվը ցույց կտա թե քանի տարբեր տեսակի միրգ կկարողանա ճաշակել Գորիլան համարի գագաթից (արմատից) միչև համարի գագաթ մագլցելու դեպքում։

Հավելում

C++ օգտագործելիս, եթե պահանջվի ռեկուրսիա, մեծացրեք ռեկուրսիայի stack-ի չափը հետևալ ֆունկցիայի միջոցով.

#include <sys/resource.h>

void increase_stack_size(size_t size_in_bytes) {
    struct rlimit rl;
    getrlimit(RLIMIT_STACK, &rl);
    rl.rlim_cur = size_in_bytes;
    setrlimit(RLIMIT_STACK, &rl);
}

int main() {
    increase_stack_size(512L * 1024L * 1024L);
    return 0;
}

Oրինակներ

Oրինակների բացատրություն

համարով գագաթ․ համարներով տեսակներ։

համարով գագաթ․ համարով տեսակ։

համարով գագաթ․ համարներով տեսակներ։

համարով գագաթ․ համարներով տեսակներ։

Ենթախնդիրներ