{"raw_statement":[{"iden":"statement","content":"Diego has a tree with exactly $N$ nodes, numbered from $1$ to $N$, where every edge is bidirectional and has an arbitrary number $X$ written on it.\n\nDiego is wondering for every unordered pair or nodes (i,j) within the tree what is the sum of the exclusive ors between the path of nodes (i,j). For this problem a path between two nodes is a simple path (no cycles) and also the shortest path between said nodes.\n\nJust to be clear, he wants to know: $\\\\sum_{i = 1}^{N} \\\\sum_{j = i + 1}^{N} P (i, j)$ Where $P (a, b)$ represents the exclusive or of every edge within the path of node a to node b.\n\nAn integer N $(1 <= N <= 10^5)$, the amount of nodes in the tree that Diego has. Followed by $N -1$ lines, each line comes in the format u v X $(1 <= u, v <= N, u eq.not v, 1 <= X <= 10^9)$, which indicates that there is a bidirectional edge between nodes u and v which has value $X$ written on it. It is guaranteed that the input will be a tree.\n\nA single integer, the sum of the exclusive or between the path of every unordered pair of nodes.\n\nIf you don't know what an exclusive or is you can look at problem 'Xor sums' for its definition.\n\n"},{"iden":"input","content":"An integer N $(1 <= N <= 10^5)$, the amount of nodes in the tree that Diego has. Followed by $N -1$ lines, each line comes in the format u v X $(1 <= u, v <= N, u eq.not v, 1 <= X <= 10^9)$, which indicates that there is a bidirectional edge between nodes u and v which has value $X$ written on it. It is guaranteed that the input will be a tree."},{"iden":"output","content":"A single integer, the sum of the exclusive or between the path of every unordered pair of nodes."},{"iden":"note","content":"If you don't know what an exclusive or is you can look at problem 'Xor sums' for its definition."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = N $, where each edge $ e \\in E $ has a weight $ w(e) \\in \\mathbb{Z}^+ $.  \nFor any unordered pair of distinct nodes $ (i, j) $, let $ P(i, j) $ denote the XOR of all edge weights along the unique simple path between $ i $ and $ j $.\n\n**Constraints**  \n1. $ 1 \\le N \\le 10^5 $  \n2. Each edge weight satisfies $ 1 \\le w(e) \\le 10^9 $  \n3. The graph is a tree (connected, acyclic, $ |E| = N - 1 $)\n\n**Objective**  \nCompute:  \n$$\n\\sum_{1 \\le i < j \\le N} P(i, j)\n$$","simple_statement":"Given a tree with N nodes and N-1 weighted edges, find the sum of XOR values of all paths between every unordered pair of nodes.","has_page_source":false}