E - Swap on the tree

2 secs 1024 MB
Ajinoko's icon Ajinoko

問題文

NN 頂点からなる木と NN 種類の置物があります。
木の頂点には 11 から NN まで番号が付いており,i=2,3,4,...,Ni=2,3,4,...,N について,ii の親は i2\lfloor \frac{i}{2} \rfloor です。x\lfloor x \rfloor とは,xx の小数点以下を切り捨てた整数値です。
置物にも 11 から NN まで番号が付いており,j=1,2,...,Nj=1,2,...,N について,置物 jj は頂点 AjA_j に置かれています。このとき,各頂点にはただ 11 つの置物が置かれていることが保証されています。
Ajinoko君は木と置物に対して次の操作を 00 回以上行うことができます。

  • 頂点 11 以外の頂点を 11 つ選ぶ。選んだ頂点を vv とすると,頂点 vv に置かれている置物と,頂点 vv の親に置かれている置物を入れ替える。

Ajinoko君が次の目標を達成するまでに必要な操作回数の最小値を求めてください。

  • 各頂点にはただ 11 つの置物が置かれており,j=1,2,...,Nj=1,2,...,N について,置物 jj は頂点 BjB_j に置かれている。

なお,適当に操作を行うと目標を達成できることは証明できます。

制約

  • 2N82 \leq N \leq 8
  • 1AiN1 \leq A_i \leq N
  • 1BjN1 \leq B_j \leq N
  • iiAiAii \neq i' \Rightarrow A_i \neq A_{i'}
  • jjBjBjj \neq j' \Rightarrow B_j \neq B_{j'}
  • 入力はすべて整数

入力

NN
A1A_1A2A_2A3A_3 ... ANA_N
B1B_1B2B_2B3B_3 ... BNB_N

出力

目標を達成するまでに必要な操作回数の最小値を出力してください。

サンプル1

入力
4
1 2 3 4
4 3 1 2
出力
3

はじめは置物 11 は頂点 11 ,置物 22 は頂点 22 ,置物 33 は頂点 33 ,置物 44 は頂点 44 にあります。
以下の順で操作を行うことで目標を達成できます。

  • 頂点 44 を選ぶ。頂点 44 にある置物 44 と,その親頂点 22 にある置物 22 を入れ替える。
  • 頂点 33 を選ぶ。頂点 33 にある置物 33 と,その親頂点 11 にある置物 11 を入れ替える。
  • 頂点 22 を選ぶ。頂点 22 にある置物 44 と,その親頂点 11 にある置物 33 を入れ替える。

上記の操作回数は 33 回であり,これより少ない操作回数で目標を達成することはできません。

サンプル2

入力
5
2 3 5 1 4
2 3 5 1 4
出力
0

はじめから目標を達成しています。

サンプル3

入力
7
4 2 6 3 5 1 7
6 7 5 2 4 3 1
出力
11

Submit


Go (1.21)