QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 1024 MB Total points: 100
[+9]

# 5017. 相等树链

Statistics

题目描述

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

一个点的子集 STi 上为一条链,当且仅当存在 1xyn,在 Ti 上从 xy 的最短路径经过的点集恰好为 S

输入格式

第一行一个整数 n

接下来两行,每行各 n1 个整数。不妨设 T1,T2 的根结点均为 1,那么其中第 i 行的第 j 个数表示在 Tij+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}

附加样例

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

限制

对于所有数据,1n2×105,1pi,jn

Subtask #1 (10 分):n5000

Subtask #2 (20 分):T1,T2 中每个点的度数均不超过 2

Subtask #3 (30 分):T1,T2 中每个点的度数均不超过 3

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