#PQJ1032x5017. QOJ 1032_5017

    ID: 2530 传统题 6000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2022-2023 集训队互测最短路径

QOJ 1032_5017

标题: 相等树链 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

题目描述

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