CF1303G Sum of Prefix Sums

We define the sum of prefix sums of an array $ [s_1, s_2, \dots, s_k] $ as $ s_1 + (s_1 + s_2) + (s_1 + s_2 + s_3) + \dots + (s_1 + s_2 + \dots + s_k) $ . You are given a tree consisting of $ n $ vertices. Each vertex $ i $ has an integer $ a_i $ written on it. We define the value of the simple path from vertex $ u $ to vertex $ v $ as follows: consider all vertices appearing on the path from $ u $ to $ v $ , write down all the numbers written on these vertices in the order they appear on the path, and compute the sum of prefix sums of the resulting sequence. Your task is to calculate the maximum value over all paths in the tree.

N/A

N/A

The best path in the first example is from vertex $ 3 $ to vertex $ 1 $ . It gives the sequence $ [3, 3, 7, 1] $ , and the sum of prefix sums is $ 36 $ .