题目描述

给定 $2$ 棵点集均为 $\{1,2,⋯,n\}$ 的树 $T_1,T_2$。问有多少个点的非空子集在 $T_1,T_2$ 上均为一条链。

一个点的子集 $S$ 在 $T_i$ 上为一条链，当且仅当存在 $1≤x≤y≤n$，在 $T_i$ 上从 $x$ 到 $y$ 的最短路径经过的点集恰好为 $S$。

输入格式

第一行一个整数 $n$。

接下来两行，每行各 $n−1$ 个整数。不妨设 $T_1,T_2$ 的根结点均为 $1$，那么其中第 $i$ 行的第 $j$ 个数表示在 $T_i$ 上 $j+1$ 的父亲结点。

输出格式

一行一个整数，表示答案。

样例数据

样例 1 输入

7
7 1 3 1 7 1
3 5 3 1 5 3

样例 1 输出

11

样例 1 解释

合法的 $S$ 有 $\{1\},\{2\},\{3\},\{4\},\{5\},\{6\},\{7\},\{1,5\},\{3,4\},\{1,3,5\},\{1,3,4,5\}$。

附加样例

下发⽂件中有 $10^4$ 组 $n=10$ 的数据存放在 ex_tree1.in/out 中。

限制

对于所有数据，$1≤n≤2×10^5,1≤p_{i,j}≤n$。

Subtask #1 (10 分)：$n \leq 5\,000$。

Subtask #2 (20 分)：$T_1,T_2$ 中每个点的度数均不超过 $2$。

Subtask #3 (30 分)：$T_1,T_2$ 中每个点的度数均不超过 $3$。

Subtask #4 (40 分)：无特殊性质。