Cho một cây có trọng số gồm \(N\) đỉnh, đánh số từ \(0\) đến \(N-1\). Với mỗi \(1\le i<N\), đỉnh \(i\) nối với cha \(P[i]\) bằng một cạnh có trọng số \(W[i]\), trong đó \(P[i]<i\) và \(W[i]\ge 0\). Đỉnh \(0\) không có cha; để thuận tiện, đặt \(P[0]=W[0]=-1\).

Sasaki chỉ có thể di chuyển giữa các đỉnh bằng cách dịch chuyển tức thời. Với mức năng lượng \(e\), Sasaki có thể dịch chuyển từ đỉnh \(u\) đến đỉnh \(v\) khi và chỉ khi đồng thời thỏa mãn:

• \(u\) là tổ tiên của \(v\), hoặc \(v\) là tổ tiên của \(u\);
• XOR theo bit của trọng số tất cả các cạnh trên đường đi giữa \(u\) và \(v\) không vượt quá \(e\).

Một đỉnh được coi là tổ tiên của chính nó. Phép dịch chuyển không tiêu hao năng lượng: sau mỗi lần dịch chuyển, Sasaki vẫn có mức năng lượng \(e\).

Cụ thể, \(u\) là tổ tiên của \(v\) nếu \(u=v\), hoặc \(u=P[v]\), hoặc \(u=P[P[v]]\), và tương tự sau một số lần đi từ một đỉnh lên cha của nó.

XOR theo bit của hai số nguyên không âm \(a,b\), ký hiệu \(a\oplus b\), có bit thứ \(k\) bằng \(1\) khi đúng một trong hai bit thứ \(k\) của \(a,b\) bằng \(1\), và bằng \(0\) trong trường hợp còn lại. Chẳng hạn:

XOR của nhiều số được thực hiện liên tiếp. Vì phép XOR có tính giao hoán và kết hợp, thứ tự các số và thứ tự thực hiện phép toán không ảnh hưởng đến kết quả cuối cùng.

Miyano cần trả lời \(Q\) truy vấn. Mỗi truy vấn cho hai đỉnh \(U,V\). Hãy tìm mức năng lượng nhỏ nhất để Sasaki có thể đi từ \(U\) đến \(V\) bằng không hoặc nhiều lần dịch chuyển.

Yêu cầu cài đặt

Bạn cần cài đặt hai hàm sau:

void init(int N, std::vector<int> P, std::vector<int> W);
int minimum_energy(int U, int V);

• init nhận số đỉnh, mảng cha và mảng trọng số. Hàm được gọi đúng một lần trước mọi lời gọi minimum_energy.
• minimum_energy nhận hai đỉnh của một truy vấn và phải trả về đáp án của truy vấn đó. Hàm được gọi đúng \(Q\) lần.

Bài nộp không được cài đặt hàm main và phải khai báo #include "teleport.h".

Giới hạn

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

Chấm điểm

Ví dụ

Xét lời gọi khởi tạo:

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

Sau đó:

• minimum_energy(2, 4) trả về 1. Có thể dịch chuyển \(2\to0\) rồi \(0\to4\); XOR trên mỗi đường đi đều bằng \(1\).
• minimum_energy(3, 0) trả về 0, vì XOR trên đường \(3\to0\) bằng \(0\).
• minimum_energy(1, 1) trả về 0, vì điểm đầu và điểm cuối trùng nhau.
• minimum_energy(0, 5) trả về 0, vì XOR trên đường \(0\to5\) là \(3\oplus2\oplus1=0\).

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

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]

Với mỗi truy vấn, trình chấm in giá trị do minimum_energy trả về trên một dòng.

Nguồn: Southeast Asia Team Selection Test 2026, Ngày 1, bài XOR Teleport.