Ancestor Distance Discrepancy in Rooted Trees

You are given two rooted trees S and T each with n nodes. In tree S, for each node i (1-indexed) its parent is given as p_i with the property that the root has p_i = 0. Similarly, in tree T, each node i has parent q_i where the root satisfies q_i = 0.

For a given rooted tree T, we say that a node u is an ancestor of node v if, by repeatedly moving from a node to its parent starting at v, you eventually reach u. In particular, if u and v satisfy this relation (i.e. one is on the upward path of the other), we say that the pair {u, v} is in an ancestor relationship on tree T.

Define the ancestor relationship distance d_T(u, v) on tree T as follows:

[ d_T(u, v) = \begin{cases} 0, & \text{if } u \text{ and } v \text{ are in an ancestor relationship in } T,
\min{\text{steps from } u \text{ to } \textrm{lca}(u, v),, \text{steps from } v \text{ to } \textrm{lca}(u, v)}, & \text{otherwise.} \end{cases} ]

Here, \(\textrm{lca}(u,v)\) denotes the lowest common ancestor of u and v in the tree.

Given an error parameter k and the two trees S and T, define the distance function between the two trees as the number of unordered pairs of distinct nodes \(\{u, v\}\) such that one tree has u and v in an ancestor relationship (i.e. the corresponding \(d\) value is 0) while in the other tree the ancestor relationship distance is more than k. In other words, count the pairs \(\{u, v\}\) satisfying either:

[ d_S(u,v) = 0 \text{ and } d_T(u,v) > k \quad \text{or} \quad d_T(u,v) = 0 \text{ and } d_S(u,v) > k. ]

Your task is to compute this distance between the two trees.

inputFormat

The first line contains two integers n and k (number of nodes and the error parameter).

The second line contains n integers: p₁, p₂, ..., p_n where p_i=0 indicates that node i is the root of tree S, otherwise it indicates the parent of node i (the nodes are 1-indexed).

The third line contains n integers: q₁, q₂, ..., q_n in a similar format representing tree T.

outputFormat

Output a single integer which is the computed distance function value, i.e. the number of differing node pairs as defined above.

sample

3 0
0 1 1
0 1 1

0