You get a tree on nodes 1 .. n as a list of n - 1 undirected edges. You want to add as many new edges as possible so that the graph stays bipartite and simple (no self-loops, no edge added twice or on top of an existing one).
Write max_edges_to_add(n, edges) -> int.
max_edges_to_add(3, [(1, 2), (1, 3)]) # 0 (2 and 3 are on the same side)
max_edges_to_add(5, [(1, 2), (2, 3), (3, 4), (4, 5)])
# 2 (1-4 and 2-5)
n goes up to 100,000 and the tree may be one long path, so avoid deep recursion. The answer can exceed 2^31 (use 64-bit integers in C++ or Java).
Show hint
A tree has only one way to split its nodes into two sides (up to swapping them), and the added edges can't change that split. Count which pairs are still allowed.