approach for BEERUS



Can anyone discuss their approach for this problem
from this contest


The only catch in the problem was that (node(i) OR node(j)) + (node(i) AND node(j)) = node(i) + node(j).The rest is easy to figure out.


From this I see that MST is a star with center in lightweight node.
And weight MST = Sum{node_i} + (n-2)*node_0, node_0 - is lightweight node.
Sum {node_i} - easy to get.
But how to get weight of lightweight node?


If you have \displaystyle\sum_{i}^{} node_i it should be straightforward to obtain the weights for each node.
node_i = \frac{1}{n} * \left( gohan* + trunks* - \displaystyle\sum_{i}^{} node_i\right). Now just loop over all nodes and obtain the maximum.


Can you tell me where did you learn this property that
A|B + A&B = A + B