子树训练值（subtree）

题目描述

$\text{DAMON THRONE}$ 有一棵训练树，共有 $n$ 个节点，编号为 $1$ 到 $n$。

节点 $1$ 是根节点。

第 $i$ 个节点有一个训练值 $a_i$。

树上有 $n-1$ 条边，每条边连接两个节点，保证所有节点都连通。

对于每个节点 $u$，定义它的 子树训练值 为：

$$u$$

的子树中所有节点训练值之和。

也就是说，如果把整棵树以 $1$ 为根，那么节点 $u$ 的子树包括 $u$ 自己以及所有后代节点。

现在请你求出所有节点中，子树训练值最大的节点编号以及这个最大子树训练值。

如果有多个节点的子树训练值相同且都是最大值，输出编号最小的节点。

输入格式

第一行包含一个整数 $n$，表示节点数量。

第二行包含 $n$ 个整数：$a_1,a_2,\ldots,a_n$，表示每个节点的训练值。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示节点 $u$ 和节点 $v$ 之间有一条边。

输出格式

输出一行两个整数，分别表示：

• 子树训练值最大的节点编号；
• 最大子树训练值。

输入输出样例 #1

输入 #1

7
3 2 5 4 1 6 2
1 2
1 3
2 4
2 5
3 6
3 7

输出 #1

1 23

样例解释 #1

以 $1$ 为根时，整棵树都是节点 $1$ 的子树。

节点 $1$ 的子树训练值为：

$$3+2+5+4+1+6+2=23$$

可以证明这是所有节点中最大的子树训练值。

输入输出样例 #2

输入 #2

5
-5 10 -2 3 4
1 2
1 3
2 4
2 5

输出 #2

2 17

样例解释 #2

以 $1$ 为根时，节点 $2$ 的子树包含节点：

$$2,4,5$$

它的子树训练值为：

$$10+3+4=17$$

这是最大的子树训练值。

数据范围与约定

对于所有测试数据，保证：

$$1 \le n \le 2\times 10^5\quad -10^9 \le a_i \le 10^9 \quad 1 \le u,v \le n,\quad u\ne v $$

并保证输入的边构成一棵树。

测试点	分值	$n$	$a_i$	特殊性质
$1\sim 2$	$10$	$\le 100$	$\le 1000$	无
$3\sim 4$	$20$	$\le 2000$	$\le 10^9$	$\text{A}$
$5\sim 6$		$\le 10^5$		$\text{B}$
$7\sim 8$				$\text{C}$
$9\sim 10$	$30$	$\le 2\times 10^5$		无

特殊性质 $\text{A}$：保证所有 $a_i$ 都为正数。

特殊性质 $\text{B}$：保证树是一条链，即边为 $1-2,2-3,\ldots,n-1-n$。

特殊性质 $\text{C}$：保证所有 $a_i$ 都相同。