MST on Pair Graph with Tree Subtree Difference

You are given a rooted tree with n vertices and m pairs of vertices. The tree is defined as follows: vertex 1 is the root, and for i = 2,...,n, an integer p_i is given which is the parent of vertex i.

Then, m pairs are provided in the form (xi, yi) (1 ≤ i ≤ m), where each x_i and y_i is a vertex of the tree.

For any two vertices a and b of the tree, define \[ D(a,b)=\begin{cases} \text{size}(\text{subtree}(a))-\text{size}(\text{subtree}(b)) & \text{if } b \text{ is in the subtree of } a,\\ \text{size}(\text{subtree}(a)) & \text{otherwise,} \end{cases} \] where \(\text{subtree}(x)\) denotes the set of vertices in the subtree rooted at x (including x), and \(\text{size}(\cdot)\) denotes its number of vertices. (Note that when \(a=b\), we take \(D(a,a)=0\).)

Consider a complete graph whose vertices correspond to these m pairs. The weight of the edge between the pair (xi, yi) and the pair (xj, yj) is defined as \[ W((x_i,y_i),(x_j,y_j)) = D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i). \]

Your task is to compute the total weight of the Minimum Spanning Tree (MST) of this complete graph.

Input Format:
The first line contains two integers n and m.

The second line contains n-1 integers: p2, p3, ..., pn, where pi is the parent of vertex i (the tree is rooted at vertex 1).

The following m lines each contain two integers xi yi, representing a pair of vertices.

Output Format:
Output a single integer representing the total weight of the MST on the complete graph defined above.

Note: You may assume that the input is such that a solution using an \(O(m^2)\) MST algorithm will work within the time limits.

inputFormat

The input consists of:

1. A line with two integers: n m
2. A line with n-1 integers: p2, p3, ..., pn
3. m lines, each with two integers: x_i y_i

outputFormat

Output a single integer indicating the total weight of the minimum spanning tree.

sample

5 2
1 1 2 2
2 3
4 5

5

</p>