P1071风铃九重错响（chime）

【题目背景】

旧剧院准备重演失传已久的《风铃九重错响》。旧时乐师把小铃层层相悬、回声反复折返的演奏方式称为“九重”，舞台上的风铃装置也因此搭成层层分岔的形状。每一次转动横杆都会改变音牌奏响的次序，乐师希望在开演前让其中的错音尽可能少。

【题目描述】

风铃装置中共有 $n$ 枚音牌，每枚音牌上写有一个整数，并且所有音牌上的整数恰好构成 $1\sim n$ 的一个排列。

整座装置按照递归方式搭建：

• 一枚音牌本身可以构成一座装置。
• 也可以在一根横杆的左侧与右侧各悬挂一座装置，从而构成一座更大的装置。

因此，每一根横杆的左右两侧都恰好悬挂着一座完整装置。乐师可以选择任意若干根横杆，对每根选中的横杆进行一次回旋。进行回旋后，横杆左右两侧悬挂的整座装置会交换位置，其中的内部结构不会发生其他改变。

同一根横杆没有必要进行超过一次回旋，不同横杆上的回旋可以按照任意顺序完成。

完成所有回旋后，从舞台左侧向右侧依次读出音牌上的整数，得到一个长度为 $n$ 的序列 $b_1,b_2,\ldots,b_n$。

对于两个满足 $1\leq i<j\leq n$ 的位置，若 $b_i>b_j$，那么编号较大的音牌会先于编号较小的音牌奏响，并产生一次错响。整场演奏的错响数量等于所有满足这一条件的二元组 $(i,j)$ 数量。

请你选择进行回旋的横杆，使最终产生的错响数量最少，并求出这个最小值。

【输入格式】

从文件 $\textbf{\textit{chime.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含一个非负整数 $c$ 与一个正整数 $T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含一个正整数 $n$，表示音牌数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示编号为 $i$ 的音牌上写有整数 $a_i$。

装置共有 $2n-1$ 个结点，其中编号为 $1\sim n$ 的结点是音牌，编号为 $n+1\sim2n-1$ 的结点是横杆。

接下来 $n-1$ 行，对于每个 $n+1\leq i\leq2n-1$，输入一行两个正整数 $l_i,r_i$，分别表示编号为 $i$ 的横杆左侧与右侧悬挂的结点编号。

保证 $1\leq l_i,r_i<i$，给出的关系构成一棵以 $2n-1$ 为根、以 $1\sim n$ 为叶子的二叉树。

【输出格式】

输出到文件 $\textbf{\textit{chime.out}}$ 中。

对于每组测试数据输出一行一个整数，表示能够得到的最少错响数量。

【样例 1 输入】

10 22434 1 3 241 253 465 67382 3 192 3101 4

【样例 1 输出】

1221

【说明/提示】

【样例 1 解释】

在第一组测试数据中，对下方的两根横杆分别进行一次回旋，可以使音牌依次奏响为 $1,4,2,3$。此时只有 $(4,2)$ 与 $(4,3)$ 产生错响，可以证明无法得到更少的错响。

在第二组测试数据中，将右侧装置进行一次回旋，可以得到序列 $2,1,3$，其中只有 $(2,1)$ 产生错响，因此答案为 $1$。

【样例 2】

见选手目录下的 $\textbf{\textit{chime/chime2.in}}$ 和 $\textbf{\textit{chime/chime2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{chime/chime3.in}}$ 和 $\textbf{\textit{chime/chime3.ans}}$。

该组样例符合测试点 $5\sim 9$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{chime/chime4.in}}$ 和 $\textbf{\textit{chime/chime4.ans}}$。

该组样例符合测试点 $10\sim 14$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{chime/chime5.in}}$ 和 $\textbf{\textit{chime/chime5.ans}}$。

该组样例符合测试点 $15\sim 19$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{chime/chime6.in}}$ 和 $\textbf{\textit{chime/chime6.ans}}$。

该组样例符合测试点 $20\sim 25$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq20$，$2\leq n\leq2\times10^5$，单个测试点内 $\sum n\leq2\times10^5$，所有音牌上的整数恰好构成 $1\sim n$ 的一个排列。

特殊性质：每根横杆的左侧或右侧至少有一侧直接悬挂一枚音牌。