You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1.5S/128M

题目描述

给定一棵包含 $n$ 个节点的树。初始时，每个节点 $i$ 上都设有一座炮台，其攻击半径为 $a_i$。一座位于节点 $u$、攻击半径为 $r$ 的炮台，可以覆盖树上所有与节点 $u$ 的距离不超过 $r$ 的节点 $v$。

对于每个节点 $i$，我们定义其 “ 防御需求 ” 为 $b_i$。当一个节点被至少 $b_i$ 座炮台覆盖时，我们称该节点是防御充足的。

现在，你需要依次对每个节点 $i$（从 $1$ 到 $n$）进行一次独立的计算：假设在节点 $i$ 上额外增设一座新的炮台，你需要找到一个最小的整数攻击半径 $R$，使得当这座新炮台的攻击半径设置为 $R$ 时，树上的所有节点都能变为防御充足的。

如果无论给新增的炮台设置多大的攻击半径，都无法满足所有节点的防御需求，则对于该次计算，答案为 $-1$。

由于输出量过大，你不需要逐一输出每个 $i$ 的答案。请计算出这 $n$ 个答案的异或和以及答案的和 （对于第 $i$ 个答案是 $-1$ 的情况，请将 $i$ 作为答案参与计算），并输出最终结果。

格式

输入格式

第一行包含一个整数 $n$，表示树的节点数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，分别表示初始时每个节点上炮台的攻击半径。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$，分别表示每个节点的防御需求。

接下来的 $n-1$ 行，每行包含两个整数 $u, v$，表示节点 $u$ 和节点 $v$ 之间存在一条边。

输出格式

输出两个整数，表示答案的异或和以及和。

样例

样例输入 #1

3
0 0 0
1 2 1
1 2
2 3

样例输出 #1

0 2

样例输入 #2

3
0 0 0
3 3 3
1 2
2 3

样例输出 #2

0 6

数据规模

对于 $15\%$ 的测试数据，$1 \leq n \leq 10^3$，$0 \leq a_i \leq 10^3$， $0 \leq b_i \leq 10^3 + 1$。

对于 $100\%$ 的测试数据，$1 \leq n \leq 5 \times 10^5$，$0 \leq a_i \leq 5 \times 10^5$， $0 \leq b_i \leq 5 \times 10^5 + 1$。