Keeping On Track

Note: Its unclear whether the enemy in this problem can change his selection based on knowing where you built your tracks. Based on certain wording in the problem and the solution rate, I'm assuming he CANNOT. Please update this page if you find different!

This problem asks you to determine which node in a tree splits the tree such that the new disjoint trees have a maximal sum of products of cardinality. This is the "critical junction". Clearly we cannot do n^2 try every node, as this is too slow. It seems like we need to at least examine each node, though. The duplicate work is obvious. If we are down some long branch of a tree, if we split, we'll recalculate the entire rest of the tree, even nowhere near the split. So we need a way to "try the next node" without recomputing everything, and that update needs to be sublinear time.

1. Pick some node as root
2. recurse to each child, which returns maximum split value for that subtree, as well as number of nodes in the subtree
3. calculate value if we were to blow up this junction
   1. start sum at 0, descendents seen at 0, best at max(all the childrens returns)
   2. iterate over children
   3. descendents seen += nodes_in_this_childs_subtree
   4. sum += nodes_in_this_childs_subtree * (total_nodes - descendents_seen)
   5. return descendents seen + 1 (for ourselves), and max(best,sum)

Need to also cache the node at which "best" was found. Whichever is "best" at the root node is best for the tree. Runtime is linear in number of nodes.

Finding place to build tracks should just be connecting to maximum size partitions created by removing that node.