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. answered 13 Jun, 22:21
