Kí hiệu \(\oplus\) tương ứng với phép tính XOR.

Subtask 1:

Với mỗi đỉnh \(u\), ta DFS / BFS 1 lần để tính tổng XOR trên đường đi từ \(u\) đến mọi \(v\) khác.
Gọi tổng XOR trên đường đi từ \(u\) tới \(v\) là \(S(u,v)\), ta chỉ cộng biến kết quả res thêm 1 nếu \(a \leq S(u,v) \leq b\) và \(v \geq u\)

Độ Phức Tạp \(O(n^2)\).

Subtask 2:

Cây có dạng đoạn thẳng.
Đặt \(s[u]\) là tổng XOR các đỉnh từ \(1\) đến \(u\), thì tổng xor của đoạn \([v,u] (v \leq u)\) là \(s[u] \oplus s[v – 1]\) (theo tính chất của phép XOR : \(a \oplus a = 0\))

Gọi \(f(u, x)\) là số lượng số \(s[v]\) mà \(s[v] \oplus s[u] \leq x\). Khi đó mỗi đỉnh \(u\) sẽ cộng thêm vào kết quả một lượng là \(f(u,b) – f(u,a – 1)\).

Để tính hàm \(f\), ta có thể xử dụng Trie (cây tiền tố). Mỗi số tự nhiên \(x\), ta coi như là một xâu có \(30\) kí tự \(0\) hoặc \(1\) --> bạn cài hàm insert như Trie truyền thống.

Chi tiết hàm query như sau : Tại mỗi nút trên Trie, ta lưu cnt là số lượng 'xâu' mà nút này quản lí (tức số lượng 'xâu' nhận nút này làm tiền tố). Ta thực hiện việc di chuyển trên cây Trie từ bit \(29\) về tới bit \(0\). Đặt \(y = s[u] \oplus x\). Gọi \(bu, bx\) lần lượt là bit \(i\) của \(s[u]\) và \(x\), như vậy tại bước này ta sẽ đi vào nhánh con \(by = bu \oplus bx\). Nếu \(bx = 1\), ta cộng vào kết quả số lượng số trên nhánh còn lại (cnt) (vì mọi số trong nhánh này sẽ đảm bảo cho ra tổng XOR bé hơn \(x\)). Sau khi đi tới cuối cùng, ta cộng kết quả thêm cnt (số lượng số bằng \(y\)).

ĐPT \(O(n \times 30)\)

Để giải được subtask cuối, bạn cần kiến thức về Centroid Decomposition (chia để trị trên cây).

Subtask 3:

Xét nút \(u\). Nhận thấy, mọi nút \(L\) trong nhánh con trái của \(u\), và mọi nút \(R\) trong nhánh con phải của \(u\), luôn thỏa mãn \(lca(L,R) = u\). Do đó đường đi giữa mọi cặp \((L,R)\) bất kỳ có thể tách ra thành hai đường đi : từ \(L\) tới \(u\) và từ \(R\) tới \(u\).

Vì thế ta có ý tưởng cài đặt dùng Trie như sau :

Ta thực hiện việc DFS trên cây. (Để thuận tiện, gọi \(W[v]\) là tổng XOR tất cả các đỉnh trên đường đi từ \(u\) tới \(v\), \(v\) là con cháu của \(u\)). Tại nút \(u\), ta thêm tổng XOR của tất cả đường đi bắt đầu từ \(u\), kết thúc ở nhánh trái vào Trie (chính là tất cả \(W[L]\)). Sau đó, tại mỗi nút \(R\) trong nhánh phải, ta xem thử có bao nhiêu nút \(L\) trong nhánh trái, mà \(W[L] \oplus W[R] \oplus l[u] \leq x\)?

ĐPT \(O(30 \times n \times log)\)

Chứng minh ĐPT : Mỗi nút \(u\) chỉ được duyệt qua trong hàm DFS gọi từ các tổ tiên của nó. Do có \(n\) nút tổng cộng, và
vì là cây nhị phân nên độ cao của cây là \(\left \lceil{log_2(n)}\right \rceil + 1\).

Subtask 4:

Ta tìm 1 nút centroid \(u\) của cây và đếm số lượng đường đi qua \(u\) (mà thỏa mãn). Đó chính là những đường đi từ 1 nút trong nhánh con \(v_i\), đến \(u\) và đi sang một nút trong nhánh con \(v_j (j \neq i)\). Sau đó, ta xoá nút centroid \(u\) đi và thực hiện tương tự với các thành phần liên thông được tách ra.

Bạn cần tổng quát hóa ý tưởng trong subtask 3 để cài đặt subtask này.

ĐPT \(O(30 \times n \times log)\)