题目描述

派蒙在一棵大树上采集晶蝶。树是由 $n$ 个节点和 $(n-1)$ 条无向边组成的连通图。

最初，第 $i$ 个节点上有 $a_i$ 只晶蝶。当派蒙到达某个节点时，可以立即捕获该节点上所有剩余的晶蝶。但晶蝶十分胆小——当派蒙到达某个节点时，所有相邻节点上的晶蝶都会受到惊扰。对于第 $i$ 个节点，若其晶蝶在第 $t'$ 秒初首次受到惊扰，则它们将在第 $(t' + t_i)$ 秒末消失。

在第 $0$ 秒初，派蒙到达节点 $1$ 并停留至第 $1$ 秒初之前。此后在每秒初，她可以选择以下两种操作之一：

• 移动到当前节点的某个相邻节点，并在下一秒初之前停留在该节点（若目标节点的晶蝶在该秒末消失，她仍可捕获）；
• 在当前节点原地停留至下一秒初。

请计算在 $10^{10^{10^{10^{10}}}}$ 秒内，派蒙最多能捕获多少只晶蝶。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示节点数。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le 10^9$），表示每个节点上的晶蝶数量。

第三行包含 $n$ 个整数 $t_1, t_2, \cdots, t_n$（$1 \le t_i \le 3$），表示每个节点的晶蝶受惊扰后消失的延迟时间。

接下来 $(n-1)$ 行，每行包含两个整数 $u_i, v_i$（$1 \le u_i, v_i \le n$），表示连接节点 $u_i$ 和 $v_i$ 的一条边。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行包含一个整数，表示派蒙最多能捕获的晶蝶数量。

样例

2
5
1 10 100 1000 10000
1 2 1 1 1
1 2
1 3
2 4
2 5
5
1 10 100 1000 10000
1 3 1 1 1
1 2
1 3
2 4
2 5

10101
10111

提示

本题答案唯一。评测使用 Special Judge 校验输出是否合法。

【样例 1 解释】

按以下策略：

• 第 $0$ 秒：到达节点 $1$，捕获 $1$ 只晶蝶；节点 $2$、$3$ 的晶蝶受到惊扰。
• 第 $1$ 秒：移动到节点 $3$，捕获 $100$ 只晶蝶。
• 第 $2$ 秒：移动到节点 $1$；节点 $2$ 的晶蝶消失。
• 第 $3$ 秒：移动到节点 $2$；节点 $4$、$5$ 的晶蝶受到惊扰。
• 第 $4$ 秒：移动到节点 $5$，捕获 $10000$ 只晶蝶；节点 $4$ 的晶蝶消失。

共捕获 $1 + 100 + 10000 = 10101$ 只。