Sum of Spanning Tree Weights in a Complete Graph

You are given an undirected complete graph \(G(V,E)\) with \(|V|=n\) nodes and a weight array \(a\) of length \(n\) where the \(i\)th element \(a_i\) is the weight assigned to node \(i\) (nodes are 1-indexed).

For any edge \(e(u,v)\) connecting nodes \(u\) and \(v\), its edge weight is defined as \(val(e)=a_u \oplus a_v\) (i.e. the bitwise XOR of \(a_u\) and \(a_v\)).

A spanning tree \(T(V,E_t)\) of \(G\) has a total weight defined as \(Val(T)=\sum_{e \in E_t} val(e)\). Your task is to compute the sum

[ S=\sum_{T} Val(T), ]

where the summation runs over all distinct spanning trees (T) of (G). Two spanning trees are considered distinct if their edge sets differ by at least one edge.

Hint: In a complete graph with \(n\) nodes, the number of spanning trees is given by Cayley’s formula \(n^{n-2}\). Moreover, by symmetry, every edge \(e(u,v)\) is contained in exactly \(\frac{2}{n}n^{n-2}=2n^{n-3}\) spanning trees. Thus, the answer can be computed as:

[ S = 2n^{n-3} \times \sum_{1\le i < j \le n} (a_i \oplus a_j). ]

Note that when \(n=1\), there is only one trivial tree (with no edges) and its weight is 0.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \(n\) \((1 \le n \le 10^3)\), the number of nodes.
2. The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) \((0 \le a_i \le 10^9)\) representing the weight of each node.

outputFormat

Output a single integer, the sum \(S\) of the weights of all spanning trees in \(G\) as defined above.

sample

1
5

0