406431: GYM102409 C Xor in Tree

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.

Diego 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.

Just to be clear, he wants to know: $$$\sum\limits_{i=1}^N \sum\limits_{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.

An integer N $$$(1\le N \le 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 \le u,v \le N, u \neq v, 1 \le X \le 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.

A single integer, the sum of the exclusive or between the path of every unordered pair of nodes.

4
1 2 1
2 3 4
2 4 2

21

If you don't know what an exclusive or is you can look at problem 'Xor sums' for its definition.