CF1092F Tree with Maximum Cost

You are given a tree consisting exactly of $ n $ vertices. Tree is a connected undirected graph with $ n-1 $ edges. Each vertex $ v $ of this tree has a value $ a_v $ assigned to it. Let $ dist(x, y) $ be the distance between the vertices $ x $ and $ y $ . The distance between the vertices is the number of edges on the simple path between them. Let's define the cost of the tree as the following value: firstly, let's fix some vertex of the tree. Let it be $ v $ . Then the cost of the tree is $ \sum\limits_{i = 1}^{n} dist(i, v) \cdot a_i $ . Your task is to calculate the maximum possible cost of the tree if you can choose $ v $ arbitrarily.

N/A

N/A

Picture corresponding to the first example:  You can choose the vertex $ 3 $ as a root, then the answer will be $ 2 \cdot 9 + 1 \cdot 4 + 0 \cdot 1 + 3 \cdot 7 + 3 \cdot 10 + 4 \cdot 1 + 4 \cdot 6 + 4 \cdot 5 = 18 + 4 + 0 + 21 + 30 + 4 + 24 + 20 = 121 $ . In the second example tree consists only of one vertex so the answer is always $ 0 $ .