== include(page="template/taskheader" task_id="sezon") ==
Poveste şi cerinţă...
Î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{~1~}, ... 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{~1~}, ..., 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.
h2. Date de intrare
Fişierul de intrare $sezon.in$ ...
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{~1~} v{~2~} ... 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$.
h2. Date de ieşire
În fişierul de ieşire $sezon.out$ ...
Î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.
h2. 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":parsare-fisier-intrare (atât pentru utilizatorii de C++ şi sintaxă similară cu fstream, cât şi pentru iubitorii de C pur)*
h3. Subtask 1 (7 puncte)
* $N ≤ 3$
h3. 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
h3. Subtask 3 (18 puncte)
* $N ≤ 2 000$
* Suma valorilor $N$ pentru cele $T$ scenarii este cel mult $8 000$.
h3. 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.
h3. Subtask 5 (37 puncte)
* Fără restricţii suplimentare.
h2. Exemplu
table(example). |_. sezon.in |_. sezon.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 1
6
11 6 5 3 10 9
1 2
2 3
2 4
1 5
5 6
| 1 |
| 2
9
10 9 8 13 1 7 12 14 6
1 2
1 4
2 3
3 5
3 6
6 9
4 7
4 8
4
5 4 5 3
1 2
1 3
2 4
| 10 |
h3. 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
h3. Explicaţie
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.
== include(page="template/taskfooter" task_id="sezon") ==
