XOR Của Hàng Triệu LCA · canuc80k3601

Cho một cây gồm $n$ đỉnh, đánh số từ $1$ đến $n$ và được xem là có gốc tại đỉnh $1$ . Với hai đỉnh $u, v$ , ký hiệu $lca (u, v)$ là tổ tiên chung gần nhất của chúng trong cây có gốc này.

Có $q$ truy vấn nhưng các cặp đỉnh không được liệt kê trực tiếp. Input cung cấp sáu số $u_{start}, v_{start}, u_{jump}, v_{jump}, u_{add}, v_{add}$ theo đúng thứ tự đó. Đặt

u_{1} = u_{start}, v_{1} = v_{start} .

Với mỗi $i > 1$ , sinh truy vấn tiếp theo bằng

u_{i} = (u_{i - 1} \cdot u_{jump} + u_{add}) mod n + 1,

v_{i} = (v_{i - 1} \cdot v_{jump} + v_{add}) mod n + 1.

Dấu $mod n$ được thực hiện trước khi cộng $1$ , vì vậy mọi $u_{i}, v_{i}$ đều thuộc đoạn $[1, n]$ . Gọi $x_{i} = lca (u_{i}, v_{i})$ . Hãy tính

x_{1} \oplus x_{2} \oplus \dots \oplus x_{q},

trong đó $\oplus$ là phép XOR bit.

Input

Dòng đầu chứa hai số nguyên $n, q$ .
$n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a, b$ biểu diễn một cạnh vô hướng của cây.
Dòng cuối chứa sáu số nguyên theo thứ tự $u_{start}, v_{start}, u_{jump}, v_{jump}, u_{add}, v_{add}$ .

Output

In một số nguyên duy nhất: XOR của đáp án của toàn bộ $q$ truy vấn.

Constraints

$1 \leq n \leq 1 0^{5}$ .
$1 \leq q \leq 1 0^{7}$ .
Mỗi cạnh nối hai đỉnh khác nhau trong đoạn $[1, n]$ ; $n - 1$ cạnh tạo thành một cây.
$1 \leq u_{start}, v_{start} \leq n$ .
$0 \leq u_{jump}, v_{jump}, u_{add}, v_{add} \leq 1 0^{9}$ .
Các phép nhân khi sinh truy vấn phải được tính bằng kiểu số nguyên đủ lớn trước khi lấy modulo.
Input chỉ chứa một test case.

Scoring

Subtask $1$ ( $50$ điểm): $n, q \leq 1000$ .
Subtask $2$ ( $50$ điểm): không có giới hạn bổ sung.

Example

Test 1

Input

7 5
1 2
1 3
2 4
2 5
3 6
6 7
4 5 2 3 0 1

Output

Giải thích: Năm cặp được sinh lần lượt là $(4, 5), (2, 3), (5, 4), (4, 7), (2, 2)$ , có các LCA tương ứng $2, 1, 2, 1, 2$ . XOR của dãy này bằng $2$ .

Ý tưởng: Với tới $1 0^{7}$ truy vấn, chi phí $O (lo g n)$ cho mỗi LCA có thể quá lớn. Ta biến LCA thành một truy vấn cực tiểu trên dãy Euler.
Ý tưởng: Duyệt cây từ gốc $1$ . Ghi một đỉnh khi đi vào nó và ghi lại đỉnh cha sau mỗi lần quay lui; đồng thời lưu first[v], vị trí xuất hiện đầu tiên của $v$ . Trên đoạn Euler từ first[u] đến first[v], đỉnh có độ sâu nhỏ nhất chính là $lca (u, v)$ : quá trình DFS phải đi từ nhánh của một đầu mút lên tới tổ tiên chung rồi mới xuống nhánh của đầu còn lại, và không thể đi lên cao hơn LCA trong đoạn đó.
Ý tưởng: Ta xây sparse table trên các vị trí Euler, phép gộp chọn vị trí chứa đỉnh nông hơn. RMQ cực tiểu là phép idempotent nên một đoạn được trả lời bằng hai khối độ dài lũy thừa hai trong $O (1)$ . Sau đó sinh lần lượt đúng $q$ cặp; sau khi dùng $(u_{i}, v_{i})$ mới cập nhật hai giá trị bằng công thức modulo $n$ rồi cộng $1$ . Mỗi LCA được XOR ngay vào biến kết quả nên không cần lưu dãy truy vấn.
Ý tưởng: Tiền xử lý tốn $O (n lo g n)$ thời gian và bộ nhớ; phần truy vấn tốn $O (q)$ thời gian.