QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 1024 MB Total points: 100

# 5017. 相等树链

Statistics

题目描述

给定 $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 分):无特殊性质。