P8336 [Ynoi2004] 2stmst

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$ of 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 the node with index $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 in the minimum spanning tree.

Idea: nzhtl1477, Solution: ccz181078( $O(m\log n\log m+n\log n)$ ), Rainbow_qwq( $O(m\log n+n)$ ), Code: ccz181078&djq_cpp&Rainbow_qwq, Data: ccz181078. Sample explanation: The minimum spanning tree contains edges $(1,4,1), (2,3,3), (2,4,3)$. Each triple represents: the index of the first ordered pair, the index of the second ordered pair, and the edge weight. The sum of edge weights is $7$. Constraints: For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le m \le 10^5$. For any $i = 1, 2, \dots, n - 1$, $1 \le f_{i+1} < i + 1$. For any $i = 1, 2, \dots, m$, $1 \le x_i, y_i \le n$. Translated by ChatGPT 5