Diferențe pentru problema/alimentara între reviziile #52 si #60

După confruntarea finală dintre Suicide Squad și Batman, pierdută de cel din urmă, Joker și Harley Quinn s-au căsătorit și trăiesc fericiți în ceea ce a mai rămas din Gotham.

În orice familie cineva face piața, iar Joker-ul a primit această onoare (cine s-ar certa cu Harley Quinn oricum?). Astfel, ocazional, Joker-ul primește câte o listă de cumpărături, sub forma unui număr natural nenul. Deoarece Joker-ul a făcut burtică, Harley îl trimite de fiecare dată până la cea mai depărtată alimentară.

În orice familie cineva face piața, iar Joker-ul a primit această onoare (cine s-ar certa cu Harley Quinn oricum?). Astfel, ocazional, Joker-ul primește câte o listă de cumpărături, sub forma unui număr natural nenul. Deoarece Joker-ul a făcut burtică, Harley îl trimite mereu până la cea mai depărtată alimentară.

Gotham este un oraș modern, organizat sub forma unui arbore (graf conex aciclic) cu rădăcină (rădăcina este nodul 1). Nodurile reprezintă intersecțiile și sunt conectate între ele prin străzi bidirecționale, astfel încât din orice intersecție se poate ajunge în oricare alta. Toate străzile au lungime 1. Casa celor doi se află în nodul 1 (centrul monden al Gotham-ului). În Gotham există câte o alimentară în fiecare nod [$k$], cu un stoc inițial $S[~k~]$ (un număr natural nenul).

h2. Date de ieșire

În fișierul de ieșire $alimentara.out$ va conține maxim $Q$ linii reprezentând răspunsul la întrebările lui Harley (în ordinea în care apar în fișier).

Fișierul de ieșire $alimentara.out$ va conține maxim $Q$ linii reprezentând răspunsurile la întrebările lui Harley (în ordinea în care apar în fișier).

În cazul în care pentru o listă $L$ nu există nicio alimentară care să corespundă se va afișa $-1$.

* $1 ≤ $N$ ≤ 150.000$
* $1 ≤ $Q$ ≤ 300.000$

* $1 ≤ S[~k~], S, L ≤ 1.000.000$, $1$ ≤ $k$ ≤ $N$

* $1 ≤ S[~k~], S, L ≤ 1.000.000, 1 ≤ k ≤ N$

* $Pentru 20% din punctaj se garantează că [$N$], $Q$ ≤ 1.000$
* $Pentru 40% din punctaj se garantează că [$N$], $Q$ ≤ 50.000$
* $Pentru 60% din punctaj se garantează că [$N$], $Q$ ≤ 100.000$

h2. Exemplu
table(example).

|_. alimentara.in |_. alimentara.out |

|_. alimentara.in |_. alimentara.out |_. imagine |

| 7 3

  0 1
  1 4
  1 7
  5 3
  3 8
  3 3
  3 5
  2 2
  1 3 10
  2 7

0 1
1 4
1 7
5 3
3 8
3 3
3 5
2 2
1 3 10
2 7

| 2

  -1
|

-1
| !problema/alimentara?tree1.png!
|

table(example).

|_. alimentara.in |_. alimentara.out |

|_. alimentara.in |_. alimentara.out |_. imagine |

| 5 5

  0 3
  3 1
  1 2
  3 10
  1 6
  2 20
  1 4 7
  2 40
  2 991
  2 35

0 3
3 1
1 2
3 10
1 6
2 20
1 4 7
2 40
2 991
2 35

| 2

  1
  -1
  2

1
-1
2
| !problema/alimentara?tree2.png!

|

h3. Explicații pentru primul exemplu
Pentru prima întrebare există 2 alimentare posibile: 2, 5. Cea din nodul 5 este cea mai depărtată.