CF627F Island Puzzle

有一组偏远岛屿链，由 $n$ 个岛屿组成，岛屿之间通过若干双向桥连接。当前桥梁网络构成一棵树。也就是说，一共用 $n-1$ 座桥连接成对的岛屿，使得通过桥的网络可以从任意一个岛屿到达另一个任意岛屿。每个岛屿的中央都有一个相同的基座，除了一个岛屿外，其余每个岛屿的基座上都摆放着一个脆弱且独一无二颜色的雕像。剩下的一个岛屿上只有一个空基座。 岛民们希望重新排列这些雕像。为此，他们重复进行如下操作：首先，选择一个与当前空基座岛屿直接相邻的岛屿，然后小心翼翼地将该岛屿上的雕像搬运到相邻桥上的空基座上。 在仅能使用上述操作的条件下，很多情况下无法将雕像排列为期望的顺序。岛民们希望额外建造一座桥，以使最终可以用最少步数完成期望的雕像排列。请你计算：应该在哪两个岛屿之间建造新桥，以及能用最少多少步完成雕像的移动。

第一行包含一个整数 $n$（$2 \le n \le 200000$），表示岛屿总数。 第二行包含 $n$ 个以空格分隔的整数 $a_i$（$0 \le a_i \le n-1$），表示第 $i$ 个岛屿当前安放的雕像编号。如果 $a_i=0$，说明该岛屿没有雕像。保证所有 $a_i$ 互不相同。 第三行包含 $n$ 个以空格分隔的整数 $b_i$（$0 \le b_i \le n-1$），表示第 $i$ 个岛屿期望安放的雕像编号。如果 $b_i=0$，说明该岛屿期望为空。保证所有 $b_i$ 互不相同。 接下来的 $n-1$ 行，每行包含两个不同的整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$），表示第 $i$ 条桥连接的两个岛屿。所有桥组成一棵树，且保证输入中没有重复的桥。

输出一行整数： 如果不需要建新桥就能完成重新排列输出 $0\ t$，其中 $t$ 表示所需最少移动次数。 否则，输出 $u\ v\ t$（$1 \le u < v \le n$），表示应在 $u$ 和 $v$ 号岛屿间建桥，且最少所需移动次数为 $t$。 如果无论如何建桥也无法完成目标排列，输出一行 $-1$。

在第一个样例中，岛民们可以在 $1$ 号和 $3$ 号岛屿间建造一座桥，然后按如下顺序移动雕像：首先将雕像 $1$ 从 $1$ 号岛移动到 $2$ 号岛，然后将雕像 $2$ 从 $3$ 号岛移动到 $1$ 号岛，最后将雕像 $1$ 从 $2$ 号岛移动到 $3$ 号岛，共计 $3$ 步。 在第二个样例中，岛民们只需将雕像 $1$ 从 $1$ 号岛移动到 $2$ 号岛即可，不需要新建桥，总共只需 $1$ 步。 在第三个样例中，无论如何新建桥，也无法达到期望的雕像排列。 由 ChatGPT 5 翻译