Задача . G. Сумма префиксных сумм

Определим сумму префиксных сумм массива \([s_1, s_2, \dots, s_k]\) как \(s_1 + (s_1 + s_2) + (s_1 + s_2 + s_3) + \dots + (s_1 + s_2 + \dots + s_k)\).

Вам задано дерево, состоящее из \(n\) вершин. В каждой вершине \(i\) записано целое число \(a_i\). Определим значение простого пути от вершины \(u\) до вершины \(v\) следующим образом: рассмотрим все вершины на пути от \(u\) до \(v\), выпишем числа, записанные на этих вершинах, в порядке их появления на пути, и вычислим сумму префиксных сумм получившейся последовательности.

Ваша задача — найти максимальное значение по всем путям в дереве.