Infinitree

Bài toán này yêu cầu tìm khoảng cách giữa hai nút của một cây nhị phân nghiêm ngặt. Ồ, như vậy quá dễ ư?! Được rồi, giờ cây có thể là vô hạn. Cứ tiếp tục thế này thì chúng ta sẽ bắt đầu tiến lên các số aleph mất.

Trong bài toán này, một cây hoặc chỉ gồm một nút \(X\), hoặc gồm một nút \(X\) gắn với hai cây: một cây con trái và một cây con phải. Trong cả hai trường hợp, \(X\) là gốc của cây. Nếu cây không chỉ gồm một nút, gốc của hai cây con là hai nút con duy nhất của \(X\).

Có các màu được đánh số từ \(0\) đến \(\mathbf{N}\), kể cả hai đầu. Mỗi nút có đúng một màu; mỗi màu có thể xuất hiện ở không, một hoặc nhiều nút. Mỗi nút màu \(0\) (trắng) là lá, tức không có con. Mỗi nút màu \(i\), với \(1 \le i \le \mathbf{N}\), có đúng \(2\) con: con trái màu \(\mathbf{L_i}\) và con phải màu \(\mathbf{R_i}\). Gốc cây màu \(1\) (đen). Cây có thể có hữu hạn hoặc vô hạn đếm được nút.

Ví dụ, hình sau minh họa cây hữu hạn được xác định bởi \(\mathbf{L}=[3,0,0]\) và \(\mathbf{R}=[2,0,2]\). Màu \(2\) là xanh lam, màu \(3\) là vàng.

Khoảng cách giữa hai nút là số bước nhỏ nhất để đi từ nút này đến nút kia. Mỗi bước di chuyển từ một nút tới nút cha trực tiếp hoặc một nút con trực tiếp.

Các nút được đánh chỉ số bằng số nguyên dương. Gốc có chỉ số \(1\). Các nút còn lại nhận những chỉ số nguyên liên tiếp; nút gần gốc hơn được đánh trước. Trong các nút cách gốc bằng nhau, nút xa hơn về bên trái được đánh trước. Hình sau bổ sung chỉ số cho từng nút trong cây trước đó. Chỉ số của một nút không phụ thuộc vào màu.

Ví dụ khác, hình sau cho thấy \(33\) nút đầu tiên của cây vô hạn được xác định bởi \(\mathbf{L}=[3,4,2,4]\) và \(\mathbf{R}=[2,2,4,0]\). Màu \(4\) là xanh lá.

Cho \(\mathbf{L}\) và \(\mathbf{R}\) xác định một cây cùng chỉ số của hai nút khác nhau, hãy trả về khoảng cách giữa chúng.

Dữ liệu vào

Dòng đầu chứa số bộ test \(\mathbf{T}\). Sau đó là \(\mathbf{T}\) bộ test, mỗi bộ gồm ba dòng. Dòng đầu chứa \(\mathbf{N},\mathbf{A},\mathbf{B}\): lần lượt là kích thước các danh sách xác định cây và chỉ số hai nút cần tính khoảng cách. Dòng hai chứa \(\mathbf{N}\) số nguyên \(\mathbf{L_1},\mathbf{L_2},\dots,\mathbf{L_N}\); dòng ba chứa \(\mathbf{N}\) số nguyên \(\mathbf{R_1},\mathbf{R_2},\dots,\mathbf{R_N}\) như mô tả trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là khoảng cách giữa các nút chỉ số \(\mathbf{A}\) và \(\mathbf{B}\) trong cây do \(\mathbf{L}\) và \(\mathbf{R}\) xác định.

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).
• \(1 \le \mathbf{N} \le 50\).
• \(0 \le \mathbf{L_i} \le \mathbf{N}\).
• \(0 \le \mathbf{R_i} \le \mathbf{N}\).
• \(\mathbf{A} \lt \mathbf{B} \le 10^{18}\).
• Cây do \(\mathbf{L}\) và \(\mathbf{R}\) xác định có ít nhất \(\mathbf{B}\) nút.

Phân nhóm

Test Set 1 (phán quyết hiển thị)

\(\mathbf{A}=1\).

Test Set 2 (phán quyết ẩn)

\(1 \le \mathbf{A} \le 10^{18}\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng giữ nguyên điểm chính thức của Google Code Jam và tỷ lệ trên tổng điểm bài.

Ví dụ

Nguồn

Google Code Jam 2021, Chung kết thế giới, bài Infinitree.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.