题目描述
给定 $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 分)：无特殊性质。