Minimizing Tree Imbalance

Farmer John has conducted extensive research on the evolution of different cow breeds. His findings can be represented as a rooted tree with \(N\) nodes (\(2\le N\le 10^5\)), where the nodes are numbered from 1 to \(N\) and each node corresponds to a cow breed. For every node \(i\) (\(2\le i\le N\)), its parent is given as \(p_i\) (with \(1\le p_i<i\)), which indicates that breed \(i\) evolved from breed \(p_i\). We say that node \(j\) is an ancestor of node \(i\) if \(j=p_i\) or \(j\) is an ancestor of \(p_i\).

Each node \(i\) is associated with an integer \(s_i\) representing the number of spots of that breed. The imbalance of the tree is defined as the maximum value of \(|s_i-s_j|\) over all pairs \((i,j)\) such that \(j\) is an ancestor of \(i\). Farmer John does not know the exact values of \(s_i\); instead, he only knows lower and upper bounds \(l_i\) and \(r_i\) (with \(0\le l_i\le r_i\le 10^9\)) for each breed. The task is to assign an integer value \(s_i\) from the interval \([l_i,r_i]\) to each node \(i\) so that the imbalance of the tree is minimized.

Observation: Since the root is an ancestor of every other node, if we ensure that all assigned values lie in some interval of length \(D\) (say, \([c,c+D]\)), then the imbalance will be at most \(D\). In fact, an optimal strategy is to choose a value \(X\) for the root and then assign each \(s_i\) from the intersection of \([l_i,r_i]\) with \([X,X+D]\) (never choosing a value lower than \(X\)). Thus, it turns out that the tree structure is irrelevant – the whole tree can be assigned values within \([X,X+D]\) as long as every breed's interval has a nonempty intersection with \([X,X+D]\). Formally, there exists a valid assignment with imbalance \(D\) if and only if there exists an \(X\) such that for every \(i\), \[ [l_i, r_i] \cap [X,X+D] \neq \emptyset. \] This is equivalent to requiring \[ X \in \bigcap_{i=1}^{N} [l_i-D, r_i]. \] Hence, the minimum possible imbalance is given by \[ D_{min} = \max\Bigl(0, \max_{1\le i \le N}l_i - \min_{1\le i \le N}r_i\Bigr). \]

inputFormat

The first line contains an integer \(N\) (\(2\le N\le 10^5\)).

The second line contains \(N-1\) integers \(p_2, p_3, \ldots, p_N\) where \(1\le p_i < i\), representing the parent of each node \(i\) (for \(i\ge2\)).

Then follow \(N\) lines. The \(i\)-th of these lines contains two integers \(l_i\) and \(r_i\) (\(0\le l_i\le r_i\le 10^9\)), representing the lower and upper bounds for the number of spots for node \(i\).

outputFormat

Output a single integer: the minimum possible imbalance of the tree.

Recall that the imbalance is defined as the maximum \(|s_i-s_j|\) over all pairs of nodes \((i,j)\) with \(j\) being an ancestor of \(i\), where \(s_i\) is the assigned number of spots for node \(i\).

sample

2
1
5 10
1 6

0