571. Cutting One Edge for the Largest Product
Each node of a tree holds a value. Remove exactly ONE edge. The tree falls into two pieces; score the product of the two piece totals. Print the largest score possible.
4 nodes, values 3 2 1 5, edges 1-2 1-3 3-4 -> 30 cutting 1-3 gives 5 and 6
2 nodes, values 4 9 -> 36 the only edge
## Only n - 1 candidates
There are exactly n - 1 edges, so there are exactly n - 1 outcomes to compare. Nothing has
to be searched; the only question is how to price each cut quickly.
## Rooting turns an edge into a node
Root at node 1. Every edge now joins some node u other than the root to its parent, so the
n - 1 edges and the n - 1 non-root nodes are the same list.
Cutting the edge above u gives:
one piece = sub[u], the total of u's subtree
other piece = total - sub[u]
score = sub[u] * (total - sub[u])
and sub[u] is one children-first sweep:
sub[u] = value[u] + sum over children c of sub[c]
Then take the largest score over u from 2 to n. The root is skipped because there is no
edge above it.
## Do not reach for the balanced cut
The product x * (T - x) is largest when x is nearest T / 2, and it is tempting to hunt for
the subtree total closest to half. That is correct reasoning about the FUNCTION, but the
subtree totals available are whatever the tree offers, so you still have to look at all of
them. Computing the product directly is simpler and cannot be tripped by a tie.
## A trap worth naming
Some versions of this problem ask for the product modulo a large prime. Taking the maximum of the REDUCED products is wrong, because reducing does not preserve order. Here there is no modulus at all, and the constraints keep the product inside 64 bits, so the comparison is on the true values.
## Boundaries
Two nodes have one edge and no choice, so 4 9 answers 36.
A star of five nodes each worth 1 has total 5 and every cut gives 1 * 4 = 4.
## Cost
Time O(n). Space O(n).
The total reaches 100000 * 1000 = 10^8, so a product reaches about 2.5 * 10^15. Use 64 bits.
Constraints - `2 ≤ n ≤ 100000` - `1 ≤ each value ≤ 1000` - the input is always a tree
Input
The first line contains an integer n, the number of nodes.
The second line contains n integers, where the ith is the value at node i.
Each of the next n - 1 lines contains two integers u and v, an edge of
the tree. Nodes are numbered 1 to n and the tree is rooted at node 1.
Output
Print one integer, the largest product of the two piece totals.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.