P8260 [CTS2022] Burning Naqiu

**Warning: Abusing this problem to hack the judge will result in an account ban.**

You are given a rooted tree with $n$ vertices, and $m$ ordered pairs $(x_i,y_i)$, where $x_i,y_i$ are vertices of the tree. For vertices $a,b$ in the tree, define $D(a,b)$ as the number of vertices that are in the subtree rooted at $a$, but not in the subtree rooted at $b$. You need to find the minimum spanning tree of the complete graph whose vertices are these ordered pairs. The edge weight between $(x_i,y_i)$ and $(x_j,y_j)$ is $D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i)$.

The first line contains two integers $n,m$. The next line contains $n-1$ integers. The $i$-th integer denotes the parent $f_{i+1}$ of node $i+1$, and it is guaranteed that $f_{i+1}< i+1$. Then follow $m$ lines. The $i$-th line contains two integers $x_i,y_i$, representing a given ordered pair.

Output one integer, the sum of edge weights of the minimum spanning tree.

Explanation of the sample: The minimum spanning tree contains edges $(1,4,1),(2,3,3),(2,4,3)$. Each triple means: the index of the first ordered pair, the index of the second ordered pair, and the edge weight. The total weight is $7$. Constraints: For $10\%$ of the testdata, $1\le n,m\le 1000$. For another $10\%$ of the testdata, $1\le m\le 2\times 10^4$. For another $10\%$ of the testdata, $1\le m\le 5\times 10^4$. For another $20\%$ of the testdata, $m=n^2$, and all ordered pairs are distinct. For another $10\%$ of the testdata, for all $i=2\cdots n$, $f_i=i-1$. For another $10\%$ of the testdata, for all $i=2\cdots n$, $f_i=1$. For $100\%$ of the testdata, $1\le n\le 10^6,1\le m\le 10^5$. For all $i=1,2,\dots n-1$, $1\le f_{i+1}