Fişierul intrare/ieşire:invtree.in, invtree.outSursăAlgoritmiada 2017, Runda Finala, Seniors
AutorAndrei Popa, Mihai CalanceaAdăugată de
Timp execuţie pe test1 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Inv Tree

Dupa ce ai invatat la informatica despre arbori si faptul ca acestia cresc de sus in jos, afli ca ai fost mintit si acum ai in fata ta un arbore care creste invers, radacina fiind in partea de jos, iar arborele ramnificandu-se in sus. Fiecare muchie din arbore are o anumita lungime, un nod aflandu-se la o inaltime egala cu suma lungimilor muchiilor aflate pe drumul de la el pana la radacina. Sa spunem in continuare ca nodul i are inaltimea hi. Tu ai o scara de lungime H si te intrebi in ce noduri poti ajunge folosind-o. Dar pentru ca s-ar putea ca scara sa nu fie suficient de inalta pentru interesele tale, te-ai gandit la o strategie pentru a o extinde. Mai exact, poti taia o muchie a arborelui si astfel tot subarborele respectiv va cadea la pamant, iar tu vei putea aduna crengile si iti vei extinde scara cu suma lungimilor muchiilor cazute. Poti folosi inclusiv creanga taiata pentru a iti extinde scara.

Pentru ca esti foarte independent de fel, te-ai decis sa ignori legile fizicii si sa neglijezi educatia parintilor: pentru a taia o anumita muchie, tu te vei urca in nodul superior al acelei muchii (cel cu inaltime mai mare), sa il numim i, si iti vei taia, literalmente, creanga de sub picioare. Bineinteles, poti face acest lucru doar daca scara curenta este suficient de inalta pentru a te aduce in nodul i, adica H_curent >= hi.

Te intereseaza in care dintre cele N noduri ale arborelui poti ajunge, stiind ca poti aplica strategia descrisa de oricate ori vrei, fara a tine seama de cazaturile repetate pe care le vei suferi. Se considera ca poti ajunge intr-un nod i daca poti aduce scara ta la o inaltime mai mare sau egala cu hi iar nodul nu a cazut in prealabil ca urmare a taierii unei muchii.

Date de intrare

Pe prima linie a fisierului de intrare vor fi doua numere, N numarul de noduri si H inaltimea initiala a scarii.
Pe urmatoarele N - 1 linii vor fi trei numere, x, y, l, semnificand faptul ca exista o muchie de lungime l care uneste nodurile x si y.

Date de ieşire

Fisierul de iesire va contine o singura linie, pe care se va afisa un string format din cifre 0 si 1, a i-a cifra fiind 1 daca se poate ajunge in nodul i si 0 altfel.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ H ≤ 1.000.000.000
  • 1 ≤ l ≤ 1.000.000.000 pentru toate muchiile
  • Pentru teste in valoare de 12 puncte N ≤ 250
  • Pentru teste in valoare de 36 puncte N ≤ 1000
  • Radacina arborelui este nodul 1

Exemplu

invtree.ininvtree.out
5 1
1 2 1
2 3 10
1 4 9
4 5 1
11011

Explicaţie

La nodul 2 se poate ajunge fara a taia nicio muchie. Pentru a ajunge la nodurile 4 si 5 este nevoie sa tai muchia 1 - 2 si astfel iti vei mari scara cu 11 unitati, obtinand o scara de lungime 12.
Daca ai vrea la sa ajungi la nodul 3, nu ai putea taia muchiile 1 - 2 si 1 - 3 pentru ca atunci nodul ar cadea pe pamant, dar nici muchiile 1 - 4 si 4 - 5, deci nu vei putea aduna lemn pentru a-ti mari scara.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?