{"code":"24tht106bc6","name":"Cây toán tử","description":"Bạn được cho một cây có $n$ đỉnh và $n-1$ cạnh và một mảng $a$ gồm $n$ phần tử. Ban đầu giá trị của đỉnh thứ $i$ bằng $a_i$. Có hai loại truy vấn:\r\n\r\n - \"1 u v p\": Gọi $s_1, s_2, ..., s_k$ là các đỉnh trên đường đi từ $u$ đến $v$. Sau đó ta thực hiện thao tác $\\oplus$ với tất cả các giá trị của các đỉnh đó, nói cách khác ta gán cho $a_{s_1} = a_{s_1} \\oplus p, a_{s_2} = a_{s_2} \\oplus p,..., a_{s_k} = a_{s,k} \\oplus p$ ($1 \\le u,v \\le n, 0 \\le p \\le 2^{10}-1$).\r\n - \"2 u v\": Gọi $s_1, s_2, ..., s_k$ là các đỉnh trên đường đi từ $u$ đến $v$. Sau đó cần đưa ra tổng trọng số đỉnh của các nút trên đường đi từ $u$ đến $v$, nói cách khác cần đưa ra tổng $S = a_{s_1} + a_{s_2} + ... + a_{s_k}$ ($1 \\le u,v \\le n$).\r\n\r\n\r\n**Yêu cầu:** Với mỗi truy vấn loại $2$, in ra kết quả của số $S$ trên một dòng.\r\n\r\n*Biểu thức $x \\oplus y$ biểu diễn phép toán tử XOR của hai số $x$ và $y$.*\r\n\r\n#### Input\r\n\r\n - Dòng thứ nhất chứa một số nguyên dương $\\phi$ - số thứ tự của subtask chứa test đó.\r\n - Dòng thứ hai chứa một số nguyên dương $n$ ($1 \\le n \\le 10^5$).\r\n - Dòng thứ ba chứa $n$ số nguyên $a_1, a_2, ..., a_n$ ($0 \\le a_i \\le 2^{10}-1$).\r\n - $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u,v$ - mô tả một cạnh của cây.\r\n - Dòng tiếp theo chứa một số nguyên dương $q$ ($q \\le 10^5$) - số lượng truy vấn.\r\n - $q$ dòng cuối cùng, mỗi dòng chứa một truy vấn như mô tả ở trên.\r\n\r\n#### Output\r\n\r\n - Với mỗi truy vấn loại $2$, in ra kết quả truy vấn đó trên một dòng.\r\n\r\n#### Scoring\r\n\r\n - Subtask $1$ ($10\\%$ số điểm): $n,q \\le 1000$.\r\n - Subtask $2$ ($10\\%$ số điểm): cây thoả mãn điều kiện với hai cạnh $(u,v)$ bất kì $(u < v)$ thì $u = \\lfloor \\frac{v}{2} \\rfloor$.\r\n - Subtask $3$ ($15\\%$ số điểm): mọi truy vấn update (truy vấn loại 1) đều có $u = v$.\r\n - Subtask $4$ ($20\\%$ số điểm): cây thoả mãn điều kiện đỉnh $u$ được nối với đỉnh $u+1$ với mọi $1 \\le u \\le n-1$.\r\n - Subtask $5$ ($20\\%$ số điểm): cây thoả mãn điều kiện mỗi đỉnh không có nhiều hơn $2$ cạnh.\r\n - Subtask $6$ ($25\\%$ số điểm): không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n\r\n???+ question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        1\r\n        6\r\n        4 3 2 5 3 4\r\n        1 2\r\n        1 3\r\n        2 4\r\n        2 5\r\n        3 6\r\n        2\r\n        1 2 4 2\r\n        2 1 2\r\n        ```\r\n        \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        5\r\n        ```\r\n   \r\n    ??? warning \"Note\"\r\n        ![enter image description here][1]\r\n\r\n\r\n  [1]: https://cdn.lqdoj.edu.vn/media/pagedown-uploads/Untitled_Rx1FT0z.png","points":2500.0,"partial":true,"time_limit":2.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}