K. Различные значения на пути

В вершинах дерева записаны числа. Для каждого запроса $(u, v)$ нужно сказать, сколько различных значений встречается в вершинах пути из $u$ в $v$, включая концы.

В первой строке $n$ ($1 \le n \le 10^5$) — число вершин, пронумерованных от $0$ до $n-1$; корень — вершина $0$. Во второй строке $n$ чисел — значения в вершинах ($1 \le val_i \le 10^9$). В третьей строке $n-1$ чисел: $i$-е из них — родитель вершины $i$ (родитель имеет меньший номер).

В четвёртой строке $q$ ($1 \le q \le 10^5$). В следующих $q$ строках по два числа $u$ и $v$.

Для каждого запроса выведите количество различных значений на пути.