Hide

# Problem JJustice for Ants

Chimera Ant is an intelligent and hard-working species.

There is a colony of Chimera Ants living in Danang, Vietnam. With careful infrastructure planning and hard work, they have built their kingdom with $n$ towns, numbered from $1$ to $n$. The towns are connected by $n - 1$ two-way roads, such that, there is exactly one simple path between any pair of towns.

Winter is coming! The Chimera Ant Queen is planning to distribute food to the $n$ towns: the $i$-th town will receive $a_ i$ units of food.

However, the ants feel that the plan is not fair. The ants demand justice! They submit $q$ requests. In each request, $4$ towns $\ell$, $r$, $u$ and $v$ are given, such that the distance from $\ell$ to $r$ and from $u$ to $v$ are equal. Here the distance from town $a$ to town $b$ is the number of edges on the only simple path from $a$ to $b$.

Let $p_1 = u, p_2, \ldots , p_{\ell } = v$ denotes the simple path between town $u$ and town $v$; $q_1 = x, q_2, \ldots , q_{\ell } = y$ denotes the simple path between town $x$ and town $y$. The request says that for every $i$ between $1$ and $\ell$, town $p_ i$ and town $q_ i$ receive the same amount of food.

Changing the food distribution plan turns out to be a difficult problem. The Chimera Ant Queen has a non-negative integer $k$, and each second, she can change the plan by applying the following steps:

• Select an integer $t$.

• Select a town $i$.

• Either decrease or increase the amount of food distributed to town $i$ by $t \cdot k + 1$. In other words, the Chimera Ant Queen can either set $a_ i := a_ i + (t \cdot k + 1)$ or $a_ i := a_ i - (t \cdot k + 1)$. After this step, $a_ i$ must be a non-negative integer, as we cannot distribute a negative amount of food.

What is the shortest time it would take for the Chimera Ant Queen to change the food distribution plan to satisfy all the requests?

## Input

The first line of input contains $3$ integers $n$, $q$ and $k$ — the number of towns, the number of requests and the integer the Chimera Ant Queen has $(1 \le n \le 5 \cdot 10^5, 1 \le q \le 2 \cdot 10^5, 0 \le k \le 10^6)$.

The second line contains $n$ integers, $a_1, a_2, \ldots , a_ n$ $(1 \le a_ i \le 10^9)$, where $a_ i$ is the initial amount of food distributed to town $i$.

The next $n - 1$ lines contain $n - 1$ integers $p_2, p_3, \ldots p_ n$ $(1 \leq p_ i < i)$, one on each line, meaning that there is a two-way road connecting town $p_ i$ and town $i$.

Each of the next $q$ lines contains $4$ integers $u$, $v$, $x$ and $y$, describing one request $(1 \le u, v, x, y \le n)$. It is guaranteed that the two simple paths from $u$ to $v$ and from $x$ to $y$ have equal length.

The input guarantees that there is exactly one simple path between any pair of towns, and it is possible to satisfy all $q$ requests.

## Output

Output a single integer — the minimum number of seconds it would take for the Chimera Ant Queen to change the food distribution plan.

## Explanation of Sample input

There are $4$ roads: $(1, 2)$, $(1, 3)$, $(3, 4)$ and $(3, 5)$.

Since $k = 0$, in each second, the Chimera Ant Queen can either increase or decrease $a_ i$ by $1$.

An optimal solution would be to reduce $a_1$ to $1$ and $a_4$ to $1$, which would take $3$ seconds.

Sample Input 1 Sample Output 1
5 3 0
3 1 1 2 1
1
1
3
3
2 3 4 5
1 3 3 4
4 4 5 5

3

CPU Time limit 7 seconds
Memory limit 1024 MB