Tree Selection Scheme

You are given a tree with \(n\) nodes numbered from \(1\) to \(n\) with node \(1\) being the root. Each node \(i\) has an integer weight \(v_i\). You are also given an array of \(n-1\) integers such that for each node \(i\) (\(2 \le i \le n\)) the given integer denotes the parent of \(i\).

Your task is to select a subset of nodes satisfying the following conditions:

1. If a node is selected then its parent (if it exists) must be selected. (Note: the root has no parent.)
2. The weights of the selected nodes are all distinct.
3. For every selected node \(u\), consider all selected nodes in the subtree of \(u\) (including \(u\) itself). Let \(S_u\) be the set of weights of these nodes. Then \(S_u\) must form an arithmetic progression with common difference \(1\). In other words, if \(m = \min S_u\) and \(M = \max S_u\), then it must hold that \(M - m + 1 = |S_u|\).

A scheme is defined as a distinct set of selected nodes. Note that the empty set is also considered a valid scheme. Output the number of schemes that satisfy all these conditions.

Input Format: The input begins with an integer \(n\). The second line contains \(n\) space-separated integers \(v_1, v_2, \ldots, v_n\) representing the weights of each node. The third line contains \(n-1\) space-separated integers where the \(i^\text{th}\) integer (for \(i = 2,3,\ldots,n\)) indicates the parent of node \(i\).

Output Format: Output a single integer, the number of valid schemes.

inputFormat

The first line contains an integer \(n\) (the number of nodes). The second line contains \(n\) space-separated integers \(v_1, v_2, \ldots, v_n\) (the weights of the nodes). The third line contains \(n-1\) space-separated integers, where the \(i^\text{th}\) integer (for \(i = 2,3,\ldots,n\)) is the parent of node \(i\).

outputFormat

Output a single integer representing the number of valid schemes.

sample

3
1 2 3
1 1

4