Tree

Cerință

Se dă un $\bold{arbore}$ cu $N$ $\bold{noduri}$, numerotate de la $1$ la $N$. Nodul $1$ este $\bold{rădăcină}$.

$\\[0.25cm]$

Fiecare nod $u$ are asociată o valoare $C[u]$. Notăm cu $P[u]$ părintele nodului $u$. Vom defini $P[1] = 0$. Pentru două noduri $u$ și $v$, notăm cu $LCA(u, v)$ cel mai apropiat strămoș comun al acestora.

$\\[0.25cm]$

Pentru orice două noduri $u$ și $v$, fie $path_{max}(u, v)$ valoarea maximă $C[x]$ dintre toate nodurile $x$ ale $\bold{drumului}$ de la $u$ la $v$, inclusiv. Similar, fie $path_{min}(u, v)$ valoarea minimă $C[x]$ dintre toate nodurile $x$ ale drumului de la $u$ la $v$.

$\\[0.25cm]$

Se dau $Q$ interogări. Fiecare interogare este formată de două noduri $u$ și $v$. Se garantează că nici $u$ nici $v$ nu este $\bold{strămoș}$ pentru celălalt.

$\\[0.25cm]$

Pentru fiecare interogare, considerăm toate perechile de noduri $(x, y)$ astfel încât:

• $x$ aparține drumului de la $u$ la $LCA(u, v)$, excluzând $LCA(u, v)$;
• $y$ aparține drumului de la $v$ la $LCA(u, v)$, excluzând $LCA(u, v)$.

$\\[0.25cm]$

Pentru fiecare pereche, definim:

$f(x, y) = path\_max(P[x], P[y]) - \max(path\_min(x, u), path\_min(y, v))$

$\\[0.25cm]$

Pentru fiecare interogare, trebuie să determini valoarea maximală posibilă pentru $f(x, y)$.

$\\[0.25cm]$

Un $\bold{drum}$ între două noduri $u$ și $v$ este o secvența de noduri $x_1, x_2, \cdots, x_k$ astfel încât $x_1 = u, x_k= v$ și în care există câte o muchie între $x_i$ și $x_{i+1}$ pentru fiecare $i$ ($1 \leq i < k$).

$\\[0.25cm]$

Un $\bold{arbore}$ este un graf conex fără cicluri. Altfel spus, este un graf cu $N$ noduri și $N − 1$ muchii, astfel încât există exact un drum între oricare două noduri distincte.

$\\[0.25cm]$

Nodul $u$ este numit $\bold{strămoș}$ al nodului $v$ dacă și numai dacă drumul de la rădacină la trece prin $u$.

$\\[0.25cm]$

$\bold{Cel \ mai \ apropiat \ strămoș}$ $\bold{comun}$ a două noduri $u$ și $v$ este cel mai depărtat de rădăcină care este strămoș pentru ambele noduri $u$ și $v$.

Date de intrare

Prima linie conține două numere întregi $N$ și $Q$.

$\\[0.25cm]$

A doua linie conține valorile $C[1], C[2], \cdots, C[N]$.

$\\[0.25cm]$

A treia linie conține părinții $P[2], P[3], \cdots, P[N]$.

$\\[0.25cm]$

Fiecare dintre următoarele $Q$ linii conține câte două numere întregi $u$ și $v$, reprezentând o interogare.

Date de ieșire

Afișați $Q$ linii. Pe linia a $i$-a se va afișa valoarea maximă posibilă a funcției $f(x, y)$ pentru interogarea cu indicele $i$.

Exemplul 1

Date de intrare

5 2
10 5 2 8 15
1 1 2 3
2 5
2 3

Date de ieșire

5
5

Explicație

Pentru prima interogare, $(u, v) = (2, 5)$, avem $LCA(2, 5) = 1$.

$\\[0.25cm]$

Alegând $x = 2$ și $y = 3$, obținem:

Se poate demonstra că aceasta este valoarea maximă posibilă. Prin urmare, răspunsul este $5$.

$\\[0.25cm]$

Pentru cea de-a doua interogare, $(u, v) = (2, 3)$, singura pereche validă este $(x, y) = (2, 3)$. Astfel, răspunsul este tot $5$.

Exemplul 2

Date de intrare

8 4
20 10 5 15 12 25 8 30
1 2 1 4 5 6 7
3 8
8 3
3 6
3 4

Date de ieșire

17
17
8
5

Restricții și precizări

• $1 \leq N, Q \leq 250 \ 000$
• $1 \leq C[i] \leq 5 \cdot 10^8$, pentru fiecare $1 \leq i \leq N$
• $1 \leq P[i] < i$, pentru fiecare $2 \leq i \leq N$.
• $2 \leq u, v \leq N$, pentru fiecare interogare.
• Niciunul dintre nodurile $u$ și $v$ nu este strămoș al celuilalt.

Subtask-uri

Pentru unele subtask-uri, arborele are următoarele proprietăți suplimentare:

• $P[2]=P[3]=1$
• $P[i]=i-2$ pentru fiecare $4 \leq i \leq N$

Ne vom referi la un asemenea arbore la un $\bold{arbore \ special}$.