Selling Price

Problem Statement

Selling Price A software house keeps tree_nodes versions of a digital product, numbered 1 to tree_nodes . The versions form a rooted tree : version 1 is the root, and every other version was branched off exactly one earlier version. Version i has a download count values[i] , which may be negative (a version can lose more subscribers than it gains). The subtree of a version is that version together with every version derived from it, directly or indirectly. The price of a version is defined as: 0 , if the version has no child versions — that is, if it is a leaf; otherwise, the maximum product values[a] * values[b] over all pairs of two different versions a and b in its subtree (the version itself counts as one of them). Note that a and b must be two different versions, but their download counts may happen to be equal. Report the price of every version. Input Format Four lines: Line 1: the integer tree_nodes . Line 2: the integer tree_nodes - 1 , followed by that many integers — the tree