Description

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

初始时，第 $i$ 个顶点上有 $a_i$ 只晶蝶。当派蒙到达一个顶点时，她可以立即抓住该顶点上的所有剩余晶蝶。然而，晶蝶很胆小。当派蒙到达一个顶点时，所有相邻顶点上的晶蝶都会受到惊扰。对于第 $i$ 个顶点，如果晶蝶在第 $t'$ 秒开始时首次受到惊扰，它们将在 $(t' + t_{i})$ 秒结束时消失。

在第 $0$ 秒开始时，派蒙到达顶点 $1$ 并在第 $1$ 秒开始前停留在那里。然后在接下来的每一秒开始时，她可以选择以下两种操作之一：

• 移动到当前顶点的一个相邻顶点，并在下一秒开始前停留在那里（如果目的地的晶蝶将在该秒结束时消失，她仍然可以抓住它们）。
• 在当前顶点停留到下一秒开始前。

计算派蒙在 $10^{10^{10^{10^{10}}}}$ 秒内可以抓住的最多晶蝶数量。

Input Format

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

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示顶点的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$)，其中 $a_i$ 是第 $i$ 个顶点上的晶蝶数量。

第三行包含 $n$ 个整数 $t_1, t_2, \cdots, 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$。

Output Format

对于每个测试用例，输出一行，包含一个整数，表示派蒙可以抓住的最多晶蝶数量。

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

Hint

对于第一个样例测试用例，按照以下策略进行：

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

对于第二个样例测试用例，最佳策略与第一个样例测试用例相同。顶点 $2$ 的晶蝶计划在第 $3$ 秒结束时消失（而不是第 $2$ 秒），这使得派蒙可以抓住它们。

题面翻译由 ChatGPT-4o 提供。