题目描述

给定一棵 $n$ 个点的树，$1$ 号点为根。每个点有一个颜色，点 $i$ 的颜色为 $c_i$、父结点为 $p_i$。

除 $1$ 号点外，请你求出，对于每个点，有多少条起点和终点颜色相同路径经过了该点到他父亲的边。（只考虑路径起点和终点即可，对路径上经过的其他点的颜色不做要求）

输入格式

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

输出格式

输出共一行，$n-1$个整数用空格隔开，其中对于每 $i$ 个数字，表示有多少条起点和终点相同颜色路径经过了 $i+1$ 点到他父亲的边。

6
1 1 2 2 1 1
1 2 1 2 4

5 1 4 3 3

样例解释 1

以1号点,2号点之间的边为例，共有5条起点终点颜色相同的路径经过他； 分别是(1,2),(1,5),(2,6),(5,6),(3,4)

数据范围

• 对于 $30\%$ 的数据，满足 $2 \leq n \leq 10^3$。
• 对于 $60\%$ 的数据，满足 $2 \leq n \leq 10^4$。
• 对于 $100\%$ 的数据，满足 $2 \leq n \leq 10^5$，$1\leq c_i \le n$。