派蒙正在树上捕捉晶蝶，这是一种提瓦特大陆上的特殊蝴蝶。树是一个由 $n$ 个顶点和 $(n - 1)$ 条无向边组成的连通图。

Pixiv ID: 93964680

第 $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, \dots, a_n$ ($1 \le a_i \le 10^9$)，其中 $a_i$ 是第 $i$ 个顶点上的晶蝶数量。

第三行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$ ($1 \le t_i \le 3$)，其中 $t_i$ 是第 $i$ 个顶点上的晶蝶在受到惊扰后消失前的时间。

接下来的 $(n - 1)$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示树中连接顶点 $u_i$ 和 $v_i$ 的一条边。

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

输出格式

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

样例

样例输入 1

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

样例输出 1

10101
10111

说明

对于第一组样例，遵循以下策略：

• 在第 $0$ 秒：
  • 派蒙到达顶点 $1$；
  • 派蒙捕捉到 $1$ 只晶蝶；
  • 顶点 $2$ 和 $3$ 上的晶蝶受到惊扰。
• 在第 $1$ 秒：
  • 派蒙到达顶点 $3$；
  • 派蒙捕捉到 $100$ 只晶蝶。
• 在第 $2$ 秒：
  • 派蒙到达顶点 $1$；
  • 顶点 $2$ 上的晶蝶消失。
• 在第 $3$ 秒：
  • 派蒙到达顶点 $2$；
  • 顶点 $4$ 和 $5$ 上的晶蝶受到惊扰。
• 在第 $4$ 秒：
  • 派蒙到达顶点 $5$；
  • 派蒙捕捉到 $10000$ 只晶蝶；
  • 顶点 $4$ 上的晶蝶消失。

对于第二组样例，最优策略与第一组相同。顶点 $2$ 上的晶蝶计划在第 $3$ 秒末（而不是第 $2$ 秒末）消失，这使得派蒙能够捕捉到它们。