Tommy has a binary tree rooted at on
nodes. Each node has an integer weight
, and the father of node
is
. Tommy needs to disassemble this binary tree by sequentially removing edges. When an edge
is removed, the following happen, simultaneously:
units of cost are incurred;
and
are swapped.
Find the minimum units of cost necessary to disassemble the binary tree.
Constraints
Test | |
---|---|
1 - 3 | |
4 - 7 | |
8 - 11 | |
12 - 16 | |
17 - 25 |
Input Specification
The first line contains a positive integer .
The second line contains positive integers
.
The third line contains positive integers
, describing the binary tree.
Output Specification
Output the answer.
Sample Input 1
3
2 1 3
1 1
Sample Output 1
7
Comments