How to find maximum spanning tree in BEERUS?Please help

1 Like

Observe that (node_i OR node_j) + (node_i AND node_j) = node_i + node_j.
We can use this information to calculate node_i for all i.
(Hint: goten[i] + trunks[i] = n * node_i + \displaystyle\sum_{i}^{} node_i \forall i.)

Now, the edges in the required graph have weights equal to the sum of adjacent nodes. This means that the maximum spanning tree would be a star graph with the node of maximum weight at the center.