Can anyone discuss their approach for this problem

from this contest

1 Like

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.

3 Likes

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?

1 Like

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[i] + trunks[i] - \displaystyle\sum_{i}^{} node_i\right). Now just loop over all nodes and obtain the maximum.

2 Likes

Can you tell me where did you learn this property that

A|B + A&B = A + B