Lorintz Alexandru (Alex_tz307) Cerința
RAU-Gigel și Vlad sunt prieteni buni și le place tot timpul să se provoace unul pe altul. De data aceasta, RAU-Gigel a inventat o problemă interesantă de matematică.
Acesta are un arbore secret cu N noduri (numerotate de la 1 la N), în care fiecare nod are asociată o valoare (pe lângă numărul său de ordine din arbore), care este un număr natural și ii spune lui Vlad informații despre unele drumuri din acest arbore. O informație are forma x, y, val și reprezintă faptul că lanțul din arbore de la nodul x la nodul y are cel mai mare divizor comun al valorilor asociate nodurilor acestuia egal cu val, unde val este un număr natural nenul.
Vlad știe că RAU-Gigel minte câteodată și s-ar putea ca unele dintre restricțiile date să fie eronate, astfel că vrea să afle întâi folosind informațiile ce le are la îndemână dacă ar putea exista un arbore care să respecte toate restricțiile date de prietenul său.
Pentru că știe ce programator iscusit ești, Vlad ți-ar fi foarte recunoscător daca l-ai putea ajuta cu această problemă prin a scrie un program care să o rezolve cât mai eficient.
Date de intrare
Fișierul de intrare gcd_tree.in conține pe prima linie numărul T, care reprezintă numărul de scenarii de test care trebuie rezolvate.
Pentru fiecare test, prima linie a conține 2 numere N și M, reprezentând lungimea șirului secret și numărul de restricții pe care acesta trebuie să le respecte.
A doua linie conține N – 1 numere naturale, al i-lea număr reprezentând părintele nodului i + 1 din arbore (se consideră că arbore are nodurile indexate de la 1 și rădăcina în nodul 1).
Fiecare dintre următoarele M linii din test conține câte 3 numere x, y, val, capetele lanțului din arbore pe care se aplică restricția, respectiv valoarea acestei restricții.
Date de ieșire
Programul trebuie să afișeze în fișierul de ieșire gcd_tree.out, pe o singură linie, fără spații, un șir de lungime T format din valorile 0 sau 1, unde elementul de pe poziția i este 1 dacă scenariul de test cu numărul i din input admite un arbore posibil care să satisfacă toate restricțiile sau 0 în caz contrar.
Restricții și precizări
1 ≤ T ≤ 101 ≤ N, M ≤ 100.0001 ≤ x, y ≤ N1 ≤ val ≤ 20- Se notează cu
SNsuma valorilorNdin toate scenariile de test dintr-un fișier de intrare și cuSMsuma valorilorMdin toate scenariile de test dintr-un fișier de intrare. 1 ≤ SN ≤ 300.0001 ≤ SM ≤ 300.000- Pentru teste în valoare de
13puncte, arborele este un lanț simplu de forma1 – 2 – ... – N;1 ≤ N, M ≤ 1.000;1 ≤ SN, SM ≤ 3.000șival ∈ {2, 4, 8, 16}. - Pentru alte teste în valoare de
19puncte, arborele este un lanț simplu de forma1 – 2 – ... – N;1 ≤ N, M ≤ 1.000;1 ≤ SN, SM ≤ 3.000și1 ≤ val ≤ 20. - Pentru alte teste în valoare de
17puncte, arborele este un lanț simplu de forma1 – 2 – ... – Nșival ∈ {2,4,8,16}. - Pentru alte teste în valoare de
24puncte, arborele este un lanț simplu de forma1 – 2 – ... – N. - Pentru alte teste în valoare de
8puncte,1 ≤ N, M ≤ 1.000; 1 ≤ SN, SM ≤ 3.000șival ∈ {2, 4, 8, 16}. - Pentru alte teste în valoare de
6puncte,1 ≤ N, M ≤ 1.000; 1 ≤ SN, SM ≤ 3.000și1 ≤ val ≤ 20. - Pentru alte teste în valoare de
9puncte,val ∈ {2, 4, 8, 16}. - Pentru restul testelor nu există restricții suplimentare, adică se păstrează doar condițiile inițiale.
Exemplu:
gcd_tree.in
2 4 2 3 1 3 1 4 11 2 4 12 3 2 1 2 1 3 4 3 2 3
gcd_tree.out
10
Explicație
Pentru primul scenariu de test din exemplu, arborele secret ar putea avea valorile 11, 12, 132, 132 asociate nodurilor sale (scrise în ordine, de la nodul cu numărul 1 la nodul cu numărul 4).
Pentru al doilea scenariu de test se poate demonstra ușor matematic că nu există soluție.