#h5213u. ROT - Tree Rotations

时间限制：1 s       空间限制：128 MiB       标签： 数据结构 线段树 权值线段树 线段树合并 POI 2011 缺题解 

算法难度等级：0       思维难度等级：0       实现难度等级：0

题目描述

给定一颗有 $n$ 个叶节点的二叉树。每个叶节点都有一个权值 $p_i$（注意，根不是叶节点），所有叶节点的权值构成了一个 $1 \sim n$ 的排列。

对于这棵二叉树的任何一个结点，保证其要么是叶节点，要么左右两个孩子都存在。

现在你可以任选一些节点，交换这些节点的左右子树。

在最终的树上，按照先序遍历遍历整棵树并依次写下遇到的叶结点的权值构成一个长度为 $n$ 的排列，你需要最小化这个排列的逆序对数。

输入格式

第一行是一个整数 $n$，表示树的叶节点个数。

接下来若干行，使用递归的形式来读入这棵树，读入任意一个子树的信息时，初始时读入其根节点。对于一个结点 $u$，首先有一行一个整数 $x$。

• 若 $x \neq 0$，则表示 $u$ 是一个叶节点，其权值为 $x$。

• 若 $x = 0$，则表示 $u$ 不是叶节点，则接下来若干行读入其左子树信息，左子树读入结束后接下来若干行读入其右子树信息。

输出格式

输出一行一个整数表示最小的逆序对数。

样例输入输出

3
0
0
3
1
2

1

样例 1 解释

下图中，左图是初始读入的树，右图是操作后的树。

数据范围

• 对于 $30\%$ 的数据，保证 $n \leq 5 \times 10^3$。

• 对于 $100\%$ 的数据，保证 $2 \leq n \leq 2 \times 10^5$， $0 \leq x \leq n$，所有叶节点的权值是一个 $1 \sim n$ 的排列。

提示

请注意，$n$ 不是树的结点个数。