Cho một cây có trọng số gồm $N$ đỉnh, được đánh số từ $0$ đến $N - 1$. Với mọi $i$ thỏa mãn $1 \leq i \leq N-1$, đỉnh $i$ được nối với đỉnh cha $P[i]$ ($P[i] < i$) bằng một cạnh có trọng số $W[i]$ ($W[i] \geq 0$). Lưu ý rằng đỉnh $0$ không có đỉnh cha, vì vậy để thuận tiện, ta đặt $P[0] = W[0] = -1$.

Cách duy nhất để Sasaki di chuyển giữa các đỉnh của cây là thông qua dịch chuyển tức thời (teleportation). Với năng lượng $e$, Sasaki có thể dịch chuyển từ đỉnh $u$ đến đỉnh $v$ khi và chỉ khi tất cả các điều kiện sau được thỏa mãn:

• Hoặc $u$ là tổ tiên của $v$, hoặc $v$ là tổ tiên của $u$, VÀ
• Phép XOR bit của tất cả trọng số các cạnh trên đường đi từ $u$ đến $v$ là nhiều nhất là $e$.

Lưu ý rằng dịch chuyển tức thời không tiêu tốn năng lượng; Sasaki vẫn giữ nguyên năng lượng $e$ sau mỗi lần dịch chuyển.

Khi nào $u$ là tổ tiên của $v$? Đỉnh $u$ là tổ tiên của $v$ nếu ít nhất một trong các điều kiện sau là đúng:

• Đỉnh $u$ là đỉnh $v$ ($u = v$), HOẶC
• Đỉnh $u$ là cha của đỉnh $v$ ($u = P[v]$), HOẶC
• Đỉnh $u$ là cha của cha của đỉnh $v$ ($u = P[P[v]]$), HOẶC
• Đỉnh $u$ là cha của cha của cha của đỉnh $v$ ($u = P[P[P[v]]]$), HOẶC
• v.v.

Phép XOR bit là gì? Phép XOR bit của hai số nguyên không âm $a$ và $b$, ký hiệu là $a \oplus b$, được định nghĩa như sau: Khi viết $a \oplus b$ dưới dạng nhị phân, chữ số ở vị trí $2^k$ bằng $1$ nếu đúng một trong các chữ số ở vị trí $2^k$ của $a$ và $b$ là $1$, và bằng $0$ trong các trường hợp còn lại. Ví dụ:

• $3 \oplus 5 = 6$ (hệ nhị phân: $011 \oplus 101 = 110$).
• $4 \oplus 21 = 17$ (hệ nhị phân: $100 \oplus 10101 = 10001$). Phép XOR bit của nhiều số nguyên $A[0], A[1], \ldots, A[K-1]$ được định nghĩa là $A[0] \oplus A[1] \oplus A[2] \oplus \ldots \oplus A[K-1]$. Lưu ý rằng $\oplus$ là một toán tử giao hoán và kết hợp. Nghĩa là $a \oplus b = b \oplus a$ và $(a \oplus b) \oplus c = a \oplus (b \oplus c)$. Do đó, thứ tự sắp xếp các số nguyên hay thứ tự thực hiện phép XOR không làm thay đổi kết quả cuối cùng.

Miyano cần trả lời $Q$ truy vấn. Mỗi truy vấn được xác định bởi một cặp số nguyên $U$ và $V$. Nhiệm vụ của Miyano là tính năng lượng tối thiểu mà Sasaki cần để đi từ đỉnh $U$ đến đỉnh $V$ bằng cách sử dụng không hoặc nhiều thao tác dịch chuyển.

Chi tiết cài đặt

Bạn cần cài đặt thủ tục sau:

void init(int N, std::vector<int> P, std::vector<int> W)

• $N$: số lượng đỉnh của cây.
• $P$, $W$: các mảng số nguyên có độ dài $N$ xác định đỉnh cha của mỗi đỉnh và trọng số của cạnh nối chúng.
• Thủ tục này được gọi chính xác một lần ngay từ đầu, trước bất kỳ lời gọi nào đến minimum_energy.

int minimum_energy(int U, int V)

• $U$, $V$: cặp số nguyên mô tả một truy vấn.
• Thủ tục này được gọi chính xác $Q$ lần sau khi init đã được thực thi.
• Thủ tục này cần trả về câu trả lời cho truy vấn đã cho.

Giới hạn

• $2 \leq N \leq 50\;000$.
• $1 \leq Q \leq 100\;000$.
• $P[0] = -1$.
• $0 \leq P[i] < i$, với mọi $0 \leq i < N$.
• $W[0] = -1$.
• $0 \leq W[i] < 2^{20}$, với mọi $0 \leq i < N$.
• $0 \leq U, V < N$ trong mỗi truy vấn.

Nhiệm vụ con

1. (5 điểm) $N \leq 10$.
2. (9 điểm) $W[i] \leq 1$, với mọi $0 \leq i < N$.
3. (15 điểm) $N \leq 200$.
4. (28 điểm) $W[i] < 128$, với mọi $0 \leq i < N$.
5. (28 điểm) $N \leq 10\;000$.
6. (15 điểm) Không có giới hạn bổ sung.

Ví dụ

Xét các lời gọi sau:

init(6, [-1, 0, 1, 0, 1, 2], [-1, 3, 2, 0, 2, 1])

Cây gồm $6$ đỉnh, được minh họa dưới đây:

minimum_energy(2, 4)

Sasaki có thể di chuyển từ đỉnh $2$ đến đỉnh $4$ với năng lượng $1$ bằng cách sử dụng các lần dịch chuyển như sau:

• Dịch chuyển từ đỉnh $2$ đến đỉnh $0$. Đỉnh $0$ là tổ tiên của đỉnh $2$ và phép XOR bit của trọng số các cạnh từ đỉnh $2$ đến đỉnh $0$ là $2 \oplus 3 = 1$.
• Dịch chuyển từ đỉnh $0$ đến đỉnh $4$. Đỉnh $0$ là tổ tiên của đỉnh $4$ và phép XOR bit của trọng số các cạnh từ đỉnh $0$ đến đỉnh $4$ là $3 \oplus 2 = 1$.

Không có chuỗi dịch chuyển nào khác sử dụng ít năng lượng hơn. Do đó, lời gọi này trả về $1$.

minimum_energy(3, 0)

Sasaki có thể di chuyển từ đỉnh $3$ đến đỉnh $0$ với năng lượng $0$ bằng cách sử dụng các lần dịch chuyển như sau:

• Dịch chuyển từ đỉnh $3$ đến đỉnh $0$. Đỉnh $0$ là tổ tiên của đỉnh $3$ và phép XOR bit của trọng số các cạnh từ đỉnh $3$ đến đỉnh $0$ là $0$.

Do đó, lời gọi này trả về $0$.

minimum_energy(1, 1)

Vì đỉnh bắt đầu và đỉnh kết thúc đều là đỉnh $1$, Sasaki không cần thực hiện bất kỳ lần dịch chuyển nào, đòi hỏi năng lượng bằng $0$. Do đó, lời gọi này trả về $0$.

minimum_energy(0, 5)

Sasaki có thể di chuyển từ đỉnh $0$ đến đỉnh $5$ với năng lượng $0$ bằng cách sử dụng các lần dịch chuyển như sau:

• Dịch chuyển từ đỉnh $0$ đến đỉnh $5$. Đỉnh $0$ là tổ tiên của đỉnh $5$ và phép XOR bit của trọng số các cạnh từ đỉnh $0$ đến đỉnh $5$ là $3 \oplus 2 \oplus 1 = 0$.

Do đó, lời gọi này trả về $0$.

Ghi chú

Định dạng dữ liệu vào:

N
P[1] P[2] ... P[N - 1]
W[1] W[2] ... W[N - 1]
Q
U[0] V[0]
U[1] V[1]
...
U[Q - 1] V[Q - 1]

trong đó $U[j]$ và $V[j]$, với mọi $0 \leq j < Q$, là các đối số đầu vào cho lời gọi thứ $j$ đến minimum_energy.

Định dạng dữ liệu ra:

A[0]
A[1]
...
A[Q - 1]

trong đó $A[j]$ là câu trả lời cho truy vấn $j$, với mỗi $j$ thỏa mãn $0 \leq j < Q$.