CF1303G Sum of Prefix Sums

题目描述

我们定义一个数组 $[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$ 路径上经过的所有顶点，按路径顺序依次写下这些顶点上的数字，计算所得序列的前缀和之和。

你的任务是计算树中所有路径的值的最大值。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 150000$），表示树的顶点数。

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示树中一条连接顶点 $u_i$ 和 $v_i$ 的边。保证这些边构成一棵树。

最后一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$），依次表示每个顶点上的数字。

输出格式

输出一个整数，表示树中所有路径的最大前缀和之和。

输入输出样例 #1

输入 #1

4
4 2
3 2
4 1
1 3 3 7

输出 #1

36

说明/提示

第一个样例中，最优路径是从顶点 $3$ 到顶点 $1$。这条路径上的序列为 $[3, 3, 7, 1]$，其前缀和之和为 $36$。

由 ChatGPT 4.1 翻译