Fişierul intrare/ieşire:	sezon.in, sezon.out	Sursă	OSEPI Baraj Seniori 1
Autor	Andrei Constantinescu	Adăugată de	Matteo Verzotti •Matteoalexandru
Timp execuţie pe test	1.1 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sezon

În ţară sunt N staţiuni de schi, numerotate de la 1 la N, legate între ele prin N - 1 drumuri bidirecţionale, cu proprietatea că între oricare două staţiuni există drum direct sau indirect (n.b. ţara nu investeşte în turism mai mult decât este minim necesar). Sezonul de schi este format din M săptămâni, numerotate de la 1 la M. În fiecare săptămână Marcel Schiorul vizitează câte o staţiune de schi, notându-şi în agendă pentru fiecare staţiune care a fost ultima data când a schiat acolo. Deoarece costurile deplasării pe drumurile patriei sunt destul de mari, în săptămâni consecutive Marcel va schia în staţiuni între care există drum direct (unul dintre cele N - 1 amintite mai sus). Observaţi că Marcel nu va schia niciodată în două săptămâni consecutive în aceeaşi staţiune - ar fi plictisitor.

La finalul sezonului Marcel extrage din agendă N numere: v₁, ... v_N, unde v_i semnifică numărul săptămânii când a schiat pentru ultima dată în staţiunea i ∈ {1, ..., N}. Voi, văzând numerele din şirul v, nu îl credeţi pe cuvânt, şi vreţi să verificaţi dacă nu cumva acesta a comis o greşeală.

Date fiind N, cele N - 1 drumuri din ţară, şi numerele v₁, ..., v_N, determinaţi dacă Marcel cu siguranţă a greşit transcriind numerele v, sau dacă cele spuse de el ar putea fi adevărate. Mai mult, va trebui să rezolvaţi problema pentru T scenarii independente.

Date de intrare

Fişierul de intrare sezon.in va conţine pe prima linie T, numărul de scenarii. Urmează apoi T grupe de linii, fiecare descriind câte un scenariu de rezolvat. Pe prima linie a unui scenariu se află N, numărul de staţiuni din ţară. Pe a doua linie se află N numere separate prin spaţii: v₁ v₂ ... v_N. Pe următoarele N - 1 linii se află câte două numere a b, semnificând existenţa unui drum bidirecţional între staţiunile a şi b.

Date de ieşire

În fişierul de ieşire sezon.out se va afişa o singură linie, formată din T cifre binare. A i-a cifră, pentru 1 ≤ i ≤ T va fi '1' dacă în cel de-al i-ulea scenariu cele spuse de Marcel ar putea fi adevărate, şi '0' altfel.

Restricţii

• 1 ≤ T ≤ 15 000
• 2 ≤ N ≤ 100 000
• 2 ≤ M ≤ 100 000 000 000
• Marcel vizitează fiecare staţiune cel puţin o dată: 1 ≤ v_i ≤ M pentru i ∈ {1, ..., N}.
• Suma valorilor N pentru cele T scenarii este cel mult 400 000.
• ATENŢIE! Având în vedere testele mari se recomandă parsarea fişierului sezon.in. Puteţi folosi codul oferit de noi aici (atât pentru utilizatorii de C++ şi sintaxă similară cu fstream, cât şi pentru iubitorii de C pur)

Subtask 1 (7 puncte)

• N ≤ 3

Subtask 2 (19 puncte)

• Există exact 2 staţiuni care sunt "rupte de lume" - există câte un singur drum bidirecţional care pleacă din fiecare dintre aceste 2 staţiuni

Subtask 3 (18 puncte)

• N ≤ 2 000
• Suma valorilor N pentru cele T scenarii este cel mult 8 000.

Subtask 4 (19 puncte)

• Pentru oricare două staţiuni a, b ∈ {1, ..., N} se poate ajunge din a în b folosind cel mult 200 de drumuri directe. 

Subtask 5 (37 puncte)

• Fără restricţii suplimentare.

Exemplu

Explicaţii

Pentru primul scenariu din primul exemplu, Marcel ar putea trece, în ordine, prin staţiunile:
4, 2, 4, 2, 3, 2, 1, 5, 6, 5, 1

Pentru primul scenariu din al doilea exemplu, Marcel ar putea trece, în ordine, prin staţiunile:
5, 3, 6, 9, 6, 9, 6, 3, 2, 1, 4, 7, 4, 8

Pentru al doilea scenariu din al doilea exemplu, este imposibil ca Marcel să fie atât în staţiunea 1 cât şi în staţiunea 3 în acelaşi timp.

Cum se trimit solutii?