Minimizing Inversions in Binary Tree Preorder

You are given a binary tree with n leaf nodes. Each leaf node has an associated weight \(p_i\) (note that the root is not a leaf), and the weights of all the leaf nodes form a permutation of \(\{1,2,\dots,n\}\).

Furthermore, every node in the tree satisfies one of the following conditions: either it is a leaf, or it has both left and right children.

You are allowed to arbitrarily choose some nodes and swap their left and right subtrees. After performing these swaps, a pre-order traversal of the tree is conducted. Whenever a leaf node is encountered during this traversal, its weight is recorded, forming a permutation \(P\) of length \(n\). Your task is to decide which swaps to perform in order to minimize the number of inversion pairs in \(P\).

An inversion pair is defined as a pair of indices \((i,j)\) with \(1 \le i P[j]\). The goal is to achieve the minimum possible inversion count.

Input/Output Format

The input describes a full binary tree (each internal node has exactly two children) with exactly \(n\) leaves. The nodes are numbered from 1 to \(2n-1\) in order. The first line of input contains an integer \(n\). The following \(2n-1\) lines describe the nodes in order:

• If a line starts with 0, it represents a leaf node and is followed by an integer \(p\) denoting its weight.
• If a line starts with 1, it represents an internal node and is followed by two integers \(l\) and \(r\), the indices of its left and right children, respectively.

You may assume that the tree is rooted at node 1 and that the root is always an internal node.

The output is a single integer representing the minimum inversion count that can be achieved by performing an optimal set of subtree swaps.

inputFormat

The first line contains a single integer \(n\) (the number of leaf nodes). The following \(2n-1\) lines describe the nodes of the tree in order from 1 to \(2n-1\). Each line is in one of the following formats:

• 0 p — indicates a leaf node with weight \(p\).
• 1 l r — indicates an internal node with left child index \(l\) and right child index \(r\).

It is guaranteed that the weights of the leaf nodes form a permutation of \(\{1, 2, \dots, n\}\) and that the root (node 1) is an internal node.

outputFormat

Output a single integer: the minimum inversion count in the permutation obtained via a pre-order traversal after performing an optimal set of subtree swaps.

sample

2
1 2 3
0 2
0 1

0

</p>