{"problem":{"name":"E. Mahmoud and a xor trip","description":{"content":"Mahmoud and Ehab live in a country with _n_ cities numbered from 1 to _n_ and connected by _n_ - 1 undirected roads. It's guaranteed that you can reach any city from any other using these roads. Each ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF766E"},"statements":[{"statement_type":"Markdown","content":"Mahmoud and Ehab live in a country with _n_ cities numbered from 1 to _n_ and connected by _n_ - 1 undirected roads. It's guaranteed that you can reach any city from any other using these roads. Each city has a number _a__i_ attached to it.\n\nWe define the distance from city _x_ to city _y_ as the _xor_ of numbers attached to the cities on the path from _x_ to _y_ **(including both _x_ and _y_)**. In other words if values attached to the cities on the path from _x_ to _y_ form an array _p_ of length _l_ then the distance between them is , where is bitwise _xor_ operation.\n\nMahmoud and Ehab want to choose two cities and make a journey from one to another. The index of the start city is always less than or equal to the index of the finish city (they may start and finish in the same city and in this case the distance equals the number attached to that city). They can't determine the two cities so they try every city as a start and every city with greater index as a finish. They want to know the total distance between all pairs of cities.\n\n## Input\n\nThe first line contains integer _n_ (1 ≤ _n_ ≤ 105) — the number of cities in Mahmoud and Ehab's country.\n\nThen the second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 106) which represent the numbers attached to the cities. Integer _a__i_ is attached to the city _i_.\n\nEach of the next _n_  -  1 lines contains two integers _u_ and _v_ (1  ≤  _u_,  _v_  ≤  _n_, _u_  ≠  _v_), denoting that there is an undirected road between cities _u_ and _v_. It's guaranteed that you can reach any city from any other using these roads.\n\n## Output\n\nOutput one number denoting the total distance between all pairs of cities.\n\n[samples]\n\n## Note\n\nA bitwise _xor_ takes two bit integers of equal length and performs the logical _xor_ operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. You can read more about bitwise _xor_ operation here: [https://en.wikipedia.org/wiki/Bitwise_operation#XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).\n\nIn the first sample the available paths are:\n\n*   city 1 to itself with a distance of 1,\n*   city 2 to itself with a distance of 2,\n*   city 3 to itself with a distance of 3,\n*   city 1 to city 2 with a distance of ,\n*   city 1 to city 3 with a distance of ,\n*   city 2 to city 3 with a distance of .\n\nThe total distance between all pairs of cities equals 1 + 2 + 3 + 3 + 0 + 1 = 10.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Mahmoud 和 Ehab 生活在一个有 #cf_span[n] 座城市的国家，城市编号从 #cf_span[1] 到 #cf_span[n]，并由 #cf_span[n - 1] 条无向道路连接。保证可以通过这些道路从任意城市到达任意其他城市。每座城市有一个数字 #cf_span[ai] 与之关联。\n\n我们定义从城市 #cf_span[x] 到城市 #cf_span[y] 的距离为路径上所有城市（包括 #cf_span[x] 和 #cf_span[y]）所关联数字的 _xor_。换句话说，如果从 #cf_span[x] 到 #cf_span[y] 路径上城市的数字构成一个长度为 #cf_span[l] 的数组 #cf_span[p]，则它们之间的距离为 ，其中  是按位 _xor_ 运算。\n\nMahmoud 和 Ehab 想要选择两座城市，从其中一座出发前往另一座。起点城市的编号总是小于或等于终点城市的编号（他们可以从同一座城市出发并到达该城市，此时距离等于该城市关联的数字）。他们无法确定具体选择哪两座城市，因此尝试将每座城市作为起点，每座编号更大的城市作为终点。他们想知道所有城市对之间的总距离。\n\n第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）——Mahmoud 和 Ehab 国家中的城市数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 106]），表示与城市关联的数字。整数 #cf_span[ai] 与城市 #cf_span[i] 关联。\n\n接下来的 #cf_span[n  -  1] 行每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1  ≤  u,  v  ≤  n]，#cf_span[u  ≠  v]），表示城市 #cf_span[u] 和 #cf_span[v] 之间有一条无向道路。保证可以通过这些道路从任意城市到达任意其他城市。\n\n输出一个数字，表示所有城市对之间的总距离。\n\n按位 _xor_ 运算对两个等长的二进制整数进行操作，对每一对对应位执行逻辑 _xor_ 运算。如果仅第一个位为 #cf_span[1] 或仅第二个位为 #cf_span[1]，则结果为 #cf_span[1]；如果两个位均为 #cf_span[0] 或均为 #cf_span[1]，则结果为 #cf_span[0]。有关按位 _xor_ 运算的更多信息，请参见：https://en.wikipedia.org/wiki/Bitwise_operation#XOR。\n\n## Input\n\n第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 105]）——Mahmoud 和 Ehab 国家中的城市数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 106]），表示与城市关联的数字。整数 #cf_span[ai] 与城市 #cf_span[i] 关联。接下来的 #cf_span[n  -  1] 行每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1  ≤  u,  v  ≤  n]，#cf_span[u  ≠  v]），表示城市 #cf_span[u] 和 #cf_span[v] 之间有一条无向道路。保证可以通过这些道路从任意城市到达任意其他城市。\n\n## Output\n\n输出一个数字，表示所有城市对之间的总距离。\n\n[samples]\n\n## Note\n\n按位 _xor_ 运算对两个等长的二进制整数进行操作，对每一对对应位执行逻辑 _xor_ 运算。如果仅第一个位为 #cf_span[1] 或仅第二个位为 #cf_span[1]，则结果为 #cf_span[1]；如果两个位均为 #cf_span[0] 或均为 #cf_span[1]，则结果为 #cf_span[0]。有关按位 _xor_ 运算的更多信息，请参见：https://en.wikipedia.org/wiki/Bitwise_operation#XOR。在第一个样例中，可用的路径有：城市 #cf_span[1] 到自身，距离为 #cf_span[1]；城市 #cf_span[2] 到自身，距离为 #cf_span[2]；城市 #cf_span[3] 到自身，距离为 #cf_span[3]；城市 #cf_span[1] 到城市 #cf_span[2]，距离为 ；城市 #cf_span[1] 到城市 #cf_span[3]，距离为 ；城市 #cf_span[2] 到城市 #cf_span[3]，距离为 。所有城市对之间的总距离等于 #cf_span[1 + 2 + 3 + 3 + 0 + 1 = 10]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $ be the number of cities, and let $ a_i \\in \\mathbb{N}_0 $ for $ i = 1, 2, \\dots, n $ denote the value attached to city $ i $. The cities form a tree $ T = (V, E) $ with $ V = \\{1, 2, \\dots, n\\} $ and $ |E| = n - 1 $.\n\nFor any pair of cities $ (x, y) $ with $ 1 \\leq x \\leq y \\leq n $, define the path $ P(x, y) $ as the unique simple path from $ x $ to $ y $ in $ T $. Let $ S(x, y) $ be the multiset of vertex values along $ P(x, y) $, i.e., $ S(x, y) = \\{ a_z \\mid z \\in P(x, y) \\} $.\n\nDefine the distance $ d(x, y) $ as the bitwise XOR of all values in $ S(x, y) $:\n$$\nd(x, y) = \\bigoplus_{z \\in P(x, y)} a_z\n$$\n\nThe goal is to compute:\n$$\n\\sum_{x=1}^{n} \\sum_{y=x}^{n} d(x, y)\n$$\n\nThat is, the sum of XOR distances over all unordered pairs $ (x, y) $ with $ x \\leq y $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF766E","tags":["bitmasks","constructive algorithms","data structures","dfs and similar","dp","math","trees"],"sample_group":[["3\n1 2 3\n1 2\n2 3","10"],["5\n1 2 3 4 5\n1 2\n2 3\n3 4\n3 5","52"],["5\n10 9 8 7 6\n1 2\n2 3\n3 4\n3 5","131"]],"created_at":"2026-03-03 11:00:39"}}