g6-07634. 使带权距离和最大的根 未做

改编自 Codeforces 1092F（题面重写、数据自造；原题 URL：https://codeforces.com/problemset/problem/1092/F）

给定 $n$ 个结点的树，每个结点有权值 $a_i$。选一个点 $r$ 作根，定义代价为 ${\sum }_{i=1}^{n}dist(r,i)\cdot a_i$（$dist$ 为边数）。求代价的最大值。

输入格式：第一行 $n$；第二行 $n$ 个整数 $a_i$；接下来 $n-1$ 行 $u,v$。

输入：

3
1 1 1
1 2
1 3

输出：

3

以 $2$ 为根：$0+1+2=3$（取最大）。

数据范围：$1\le n\le 2\times 10^5$，$0\le a_i\le 10^9$（答案用 long long）。