题目描述
给定 2 棵点集均为 {1,2,⋯,n} 的树 T1,T2。问有多少个点的非空子集在 T1,T2 上均为一条链。
一个点的子集 S 在 Ti 上为一条链,当且仅当存在 1≤x≤y≤n,在 Ti 上从 x 到 y 的最短路径经过的点集恰好为 S。
输入格式
第一行一个整数 n。
接下来两行,每行各 n−1 个整数。不妨设 T1,T2 的根结点均为 1,那么其中第 i 行的第 j 个数表示在 Ti 上 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}。
附加样例
下发⽂件中有 104 组 n=10 的数据存放在 ex_tree1.in/out
中。
限制
对于所有数据,1≤n≤2×105,1≤pi,j≤n。
Subtask #1 (10 分):n≤5000。
Subtask #2 (20 分):T1,T2 中每个点的度数均不超过 2。
Subtask #3 (30 分):T1,T2 中每个点的度数均不超过 3。
Subtask #4 (40 分):无特殊性质。