题目描述

在智亦珅泽教育的算法进阶课上，小珅和小泽正在研究一棵给定的二叉树。这棵二叉树有$n$个结点，每个结点的序号为$[1, n]$中互不相同的正整数，根结点的序号为$1$，每个结点具有权值。 如果在二叉树中删除一条边，二叉树会分裂成两棵子树。定义子树和为两棵子树各自所有结点的权值之和。请你帮他们求分裂后两棵子树和的乘积的最大值。

输入格式

第1行，一个正整数$n$。

第2行，$n$个正整数$a_1, a_2, \cdots, a_n$，表示结点$i$的权值。

接下来$n$行，第$i$（$1 \le i \le n$）行两个整数$l_i$、$r_i$，表示第$i$个结点的左儿子和右儿子的编号。 若某个结点在树中没有左儿子，则对应的左儿子编号为$0$，右儿子缺失时同理。

输出格式

一行，一个整数，表示删除一条边后两棵子树和的乘积的最大值。

输入输出样例

6
1 2 3 4 5 6
2 3
4 5
6 0
0 0
0 0
0 0

110

6
1 2 3 4 5 6
0 2
3 4
0 0
5 6
0 0
0 0

90

说明/提示

对于100%的数据：

• $2 \le n \le 5 \times 10^4$
• $0 \le l_i, r_i \le n$
• $1 \le a_i \le 10^4$ 保证输入构成一棵合法的二叉树，根结点为$1$。

5
4820 2895 6662 7858 2208
2 0
3 4
5 0
0 0
0 0

138132510