P9847 [ICPC 2021 Nanjing R] Crystalfly

派蒙正在一棵树上抓晶蝶，这是一种提瓦特中特殊的蝴蝶。树是由 $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$)，其中 $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$。

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

对于第一个样例测试用例，按照以下策略进行： - 在第 $0$ 秒 - 派蒙到达顶点 $1$； - 派蒙抓住 $1$ 只晶蝶； - 顶点 $2$ 和 $3$ 的晶蝶受到惊扰。 - 在第 $1$ 秒 - 派蒙到达顶点 $3$； - 派蒙抓住 $100$ 只晶蝶。 - 在第 $2$ 秒 - 派蒙到达顶点 $1$； - 顶点 $2$ 的晶蝶消失。 - 在第 $3$ 秒 - 派蒙到达顶点 $2$； - 顶点 $4$ 和 $5$ 的晶蝶受到惊扰。 - 在第 $4$ 秒 - 派蒙到达顶点 $5$； - 派蒙抓住 $10000$ 只晶蝶； - 顶点 $4$ 的晶蝶消失。 对于第二个样例测试用例，最佳策略与第一个样例测试用例相同。顶点 $2$ 的晶蝶计划在第 $3$ 秒结束时消失（而不是第 $2$ 秒），这使得派蒙可以抓住它们。 题面翻译由 ChatGPT-4o 提供。