题目描述

给定一棵 $n$ 个点的树，$1$ 号点为根。每个点有一个颜色，点 $i$ 的颜色为 $c_i$。定义树上某两点之间的路径的分数为这条路径中出现过的不同颜色的数量。

请求出树上任意两个不同结点之间的路径分数的和。

输入格式

• 第一行：单个整数 $n$
• 第二行：$n$ 个整数，表示 $c_1,c_2,\dots,c_n$
• 第三行：$n-1$ 个整数，表示 $p_2,p_3,\dots,p_n$，其中 $p_i$ 表示结点 $i$ 的父亲，保证 $p_i<i$。

输出格式

单个整数：表示所有路径的分数之和。

3
1 2 1
1 2

6

6
1 2 3 2 1 1
1 2 2 1 5

29

数据范围

• 对于 $30\%$ 的数据，满足 $n \leq 2000$。
• 对于 $60\%$ 的数据，满足 $n \leq 200,000$，$c_i \le 50$。
• 对于 $100\%$ 的数据，满足 $2 \leq n \leq 200,000$，$1\leq c_i \le n$。