P3365 Transforming a Binary Tree

Diligent and thoughtful Xiao L started learning for the informatics competition, and the beginning went very well. However, Xiao L’s grasp of data structures was really weak. So, Xiao L got stuck on binary trees.

In computer science, a binary tree is an ordered tree in which each node has at most two children. The children are usually called the “left child” and the “right child.” Binary trees are used as binary search trees and binary heaps. Then he discussed binary search trees with others. What is a binary search tree? A binary search tree is first a binary tree. Let $key_p$ denote the value stored at node $p$. For each node $p$, if it has a left child $lch$, then $key_p > key_{lch}$; if it has a right child $rch$, then $key_p < key_{rch}$. Note that in this problem, the binary search tree must satisfy: for every node, all keys in its left subtree are less than the node’s key, and all keys in its right subtree are greater than the node’s key. But thoughtful Xiao L is not satisfied with only learning the basics. He considered this problem: given a binary tree, you can arbitrarily change the values of nodes. Changing the value of a node counts as one modification, and that node cannot be modified again. You want to transform it into a binary search tree, and at any time the value of every node must be an integer (it can be negative or $0$). What is the minimum number of modifications required? This surely won’t stump you! If you help Xiao L solve this problem, maybe he will give you $\dfrac{1}{16}$ of his final assets.

The first line contains a positive integer $n$, the number of nodes in the binary tree. The second line contains $n$ positive integers separated by spaces. The $i$-th number $a_i$ is the original value of node $i$. Then follow $n - 1$ lines, each containing two non-negative integers $fa$ and $ch$. The $(i + 2)$-th line describes the parent index $fa$ of node $i + 1$ and the parent-child relation $ch$ ($ch = 0$ means $i + 1$ is the left child, $ch = 1$ means $i + 1$ is the right child). To make it a bit easier for you, Xiao L guarantees that node $1$ is the root of the binary tree.

Output a single line containing one integer, the minimum number of modifications.

Constraints - For $20\%$ of the testdata: $n \leq 10$, $a_i \leq 100$. - For $40\%$ of the testdata: $n \leq 100$, $a_i \leq 200$. - For $60\%$ of the testdata: $n \leq 2000$. - For $100\%$ of the testdata: $n \leq 10^5$, $a_i < 2^{31}$. Translated by ChatGPT 5