Archive Tree#13102

Archive Tree (Editorial)

Root the tree at and write f_v = k_v \cdot f_p for every folder v \ne s with parent folder . Then f_v is the product of the multipliers on the path from to , and two subfolders of the same folder get different names exactly when their multipliers are different, because they share f_p. Multiplying all names in a subtree by the same number keeps the subtree valid, so the subtrees can be optimised independently. Let be the smallest possible largest name in the subtree of if f_u = 1; then h(\text{leaf}) = 1 and the answer is . If a subfolder of gets the multiplier k_c, the best its subtree can achieve is k_c \cdot h(c).

Key claim. Let g_1 \ge g_2 \ge \ldots \ge g_m be the values of the m \ge 1 subfolders of . Then

h(u) = \max_{1 \le i \le m} i \cdot g_i,

that is, the subfolder with the -th largest value gets the multiplier .

Proof. First, the multipliers 1, 2, \ldots, m suffice: the -th smallest of distinct positive integers is at least , so replacing it by keeps the multipliers distinct and increases no product. Second, the larger value should get the smaller multiplier. If g \ge g' and a < b, then

\max(a g,\, b g') \le b g \le \max(b g,\, a g'),

so swapping the multipliers of two subfolders with g \ge g' that received b > a never increases the maximum (exchange argument). After all such swaps the multipliers 1, \ldots, m go to the subfolders in the order of decreasing .

The values stay small: i \cdot g_i \le g_1 + \ldots + g_i, so by induction never exceeds the size of the subtree of . The answer is at most , although it is a product of many multipliers, and 32-bit integers suffice.

Algorithm. Run a BFS from to find the parent folders, then process the folders in reverse BFS order: collect the values of the subfolders, sort them in decreasing order and take \max_i i \cdot g_i. Every folder is sorted once as a subfolder, so the sorting costs O(n \log n) in total.

The complexity is O(n \log n) per test case.