题目描述

这里是形式化题意：

给定一棵 $n$ 个点的树，和两个长为 $n$ 的数组，数组 $cnt$ 和 数组 $A$。规定 $\text{dis(u,v)}$ 指的是树上点 $u$ 到点 $v$ 的简单路径中包含的点数。

你的任务是在点之间连一些线（不是树边），并满足如下限制：

• 每条线只能连接两个点，点 $u$ 不能连向自己。
• 两个点之间可以连接多条线。
• 与点 $u$ 相连的线的条数不能超过 $cnt_u$。

你连接的线并不会影响树本身的形态，即不会影响 $\text{dis}(u,v)$。

若你在 $(u,v)$ 间连接了一条线，那么你将得到 $(-1)^{\text{dis}(u,v)} A_uA_v$ 的得分。

现在，你想要知道你可能的最大得分是多少。

题目背景

They see your beauty, so frail and fine, They see your peace, woven of faith and toil, They forget your heart, bound in slumber and servitude, When you wake they shall see your truth, A beast's nature bare to all.

geven 是 Hollow Knight 老玩家了。最近 SilkSong 发售了，但是作为 Mac 用户的他却玩不到。念丝心切的他想出了一个好主意：自己写一个 SongSilk 自己玩。

在这个游戏中，有 $n$ 个 Boss 场景和 $n-1$ 个长椅。每个长椅两端各有⼀道传送⻔，分别可以传送到两个不同的 Boss 场景。在地图中，任意两个 Boss 场景之间可以互相到达，即所有 Boss 场景构成了⼀棵以 $1$ 为根的树。geven 认为 $\text{dis(u,v)}$ 是 Boss 场景 $u$ 到 Boss 场景 $v$ 的简单路径上经过的 Boss 场景数（包含 $u$ 和 $v$）。

geven 是 Hollow Knight 老玩家了，他早就已经无伤打败了所有 Hollow Knight Boss。然而，他不熟悉 SilkSong 的机制，保险起见，他决定在 Boss 场景间连接一些**「丝线」**，以此来降低游戏难度。

具体地，他可以连接无数条**「丝线」，每条「丝线」必须连接两个不同的 Boss 场景。但是，第 $i$ 个 Boss 场景最多只能连接 $cnt_i$ 条「丝线」**。

geven 对第 $i$ 个 Boss 场景有着 $A_i$ 的初始熟悉度。当他连接了一条连接 $(u,v)$ 的**「丝线」**，那么他将会额外获得 $(-1)^{\text{dis(u,v)}}A_uA_v$ 的熟悉度。

现在，他想知道，通过连接**「丝线」，他能额外**得到的最大熟悉度是多少。如果你正确回答了他的问题，他就会请你吃 $1000$ 串淄博烧烤，让你感受到山东人的热情好客。

七钟响时运送；

三十节又四奏烟岩，

及八奏甜熔渣。

不知所云。

输入格式

第一行一个整数 $n$，代表树上点的数量。

第二行 $n$ 个整数，代表 $cnt$ 数组。

第三行 $n$ 个整数，代表 $A$ 数组。

第四行至第 $n+2$ 行，每行两个整数 $u_i,v_i$。其中第 $i+3$ 行的输入代表树上存在一条边连接点 $u_i$ 与点 $v_i$。

输出格式

一行一个整数，代表可能的最大得分。

输入输出样例

样例输入 #1

5
1 1 1 1 1
3 -5 -2 -3 0
1 2
1 3
2 4
2 5

样例输出 #1

15

样例输入 #2

10
3 1 4 1 5 9 2 6 5 3
1 -1 4 -5 1 -4 1 -9 1 -9
1 2
1 3
1 9
2 4
2 6
3 5
3 7
3 8
8 10

样例输出 #2

303

数据范围

本题开启子任务评测。

所有测试点均满足 $1\leq n \leq 10^6$ ，$0 \leq cnt_i \leq 10^6$ ，$|A_i| \leq 10^6$ 。保证给出的边构成一棵树。

各子任务的约束条件如下：