{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e给出一棵包含 $$$n$$$ 个节点的有根树, 节点的编号为 $$$1, \\dots, n$$$. 节点 $$$1$$$ 为根. 并且每个节点 $$$i$$$ 有一个权值 $$$a_i$$$. 你发现可能会存在若干点对 $$$(i, j)$$$ 满足 $$$$$$a_i \\oplus a_j \u003d a_{\\operatorname{lca}(i, j)},$$$$$$ 其中 $$$\\oplus$$$ 表示按位异或, $$$\\operatorname{lca}(i, j)$$$ 表示 $$$i$$$ 和 $$$j$$$ 的最近公共祖先, 或者说, 拥有后代 $$$i$$$ 和 $$$j$$$ 的深度最大的节点.\u003c/p\u003e\n\u003cp\u003e不幸的是, 你没能记住所有的点对, 而只记住了 $$$\\sum i \\oplus j$$$ , 其中节点 $$$(i, j)$$$ 满足上述条件. 注意点对 $$$(i, j)$$$ 和 $$$(j, i)$$$ 被认为是相同的. 说人话, 你要计算下面的式子 $$$$$$\\sum\\limits_{i\u003d1}^n\\sum\\limits_{j\u003di+1}^n [a_i \\oplus a_j \u003d a_{\\operatorname{lca}(i, j)}] (i \\oplus j).$$$$$$\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数 $$$n$$$ ($$$2 \\leq n \\leq 10^5$$$).\u003c/p\u003e\n\u003cp\u003e第二行包含 $$$n$$$ 个整数, $$$a_1, a_2, \\ldots, a_n$$$ ($$$1 \\leq a_i \\leq 10^6$$$).\u003c/p\u003e\n\u003cp\u003e接下来 $$$n - 1$$$ 行, 每行包含 $$$2$$$ 个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \\leq u, v \\leq n, u \\neq v$$$), 表示 $$$u$$$ 和 $$$v$$$ 之间存在一条边. 保证能形成一棵树.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e输出计算的结果.\u003c/p\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e6\n4 2 1 6 6 5\n1 2\n2 3\n1 4\n4 5\n4 6\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e18\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}