{"problem":{"name":"G. Xor-MST","description":{"content":"You are given a complete undirected graph with _n_ vertices. A number _a__i_ is assigned to each vertex, and the weight of an edge between vertices _i_ and _j_ is equal to _a__i_ _xor_ _a__j_. Calcul","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF888G"},"statements":[{"statement_type":"Markdown","content":"You are given a complete undirected graph with _n_ vertices. A number _a__i_ is assigned to each vertex, and the weight of an edge between vertices _i_ and _j_ is equal to _a__i_ _xor_ _a__j_.\n\nCalculate the weight of the minimum spanning tree in this graph.\n\n## Input\n\nThe first line contains _n_ (1 ≤ _n_ ≤ 200000) — the number of vertices in the graph.\n\nThe second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ < 230) — the numbers assigned to the vertices.\n\n## Output\n\nPrint one number — the weight of the minimum spanning tree in the graph.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"给定一个具有 #cf_span[n] 个顶点的完全无向图。每个顶点被分配了一个数 #cf_span[ai]，且顶点 #cf_span[i] 与顶点 #cf_span[j] 之间的边的权重等于 #cf_span[ai xor aj]。\n\n计算该图的最小生成树的权重。\n\n第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— 图中顶点的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[0 ≤ ai < 230]) —— 分配给顶点的数。\n\n输出一个数——图中最小生成树的权重。\n\n## Input\n\n第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— 图中顶点的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[0 ≤ ai < 230]) —— 分配给顶点的数。\n\n## Output\n\n输出一个数——图中最小生成树的权重。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Given a complete undirected graph with $ n $ vertices, where each vertex $ i $ is assigned a value $ a_i \\in [0, 2^{30}) $, and the weight of edge $ (i, j) $ is $ a_i \\oplus a_j $ (XOR), compute the weight of the minimum spanning tree (MST).\n\n**Formal Statement:**\n\nLet $ V = \\{1, 2, \\dots, n\\} $, and let $ a : V \\to \\mathbb{Z} $ with $ 0 \\leq a_i < 2^{30} $.  \nDefine the edge weight function $ w : V \\times V \\to \\mathbb{Z}_{\\geq 0} $ as:  \n$$\nw(i, j) = a_i \\oplus a_j \\quad \\text{for all } i \\ne j\n$$\n\nCompute the total weight of the minimum spanning tree of the complete graph $ K_n $ with edge weights $ w(i, j) $.\n\n**Objective:**  \n$$\n\\min_{T \\in \\mathcal{T}} \\sum_{(i,j) \\in E(T)} (a_i \\oplus a_j)\n$$\nwhere $ \\mathcal{T} $ is the set of all spanning trees of $ K_n $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF888G","tags":["bitmasks","constructive algorithms","data structures"],"sample_group":[["5\n1 2 3 4 5","8"],["4\n1 2 3 4","8"]],"created_at":"2026-03-03 11:00:39"}}