[R78G]信标 - 代码源竞赛平台

时空限制

2S/512M

题目描述

一片区域中设有 $n$ 座信标，编号为 $1$ 到 $n$。信标 $i$ 显示的颜色为 $c_i$，并标明下一座信标 $f_i$；允许 $f_i=i$。

巡游者从信标 $s$ 出发，按照信标指示依次考察

$$s,\ f_s,\ f_{f_s},\ldots$$

一旦下一座要考察的信标的颜色已经在本次巡游中出现过，就立即停止，不再访问这座信标。起点本身也算访问的信标。

对于每个起点 $s=1,2,\ldots,n$，求停止前访问了多少座信标。不同起点的巡游过程互不影响。

同一种颜色可能出现在不同信标上，因此不一定要再次到达同一座信标才会停止。

格式

输入格式

第一行包含一个正整数 $n$，为信标的数量。

第二行包含 $n$ 个正整数 $f_1,f_2,\ldots,f_n$，其中 $f_i$ 表示信标 $i$ 指示的下一座信标的编号。

第三行包含 $n$ 个正整数 $c_1,c_2,\ldots,c_n$，其中 $c_i$ 表示信标 $i$ 显示的颜色。

输出格式

输出一行 $n$ 个正整数，第 $s$ 个整数表示从信标 $s$ 出发，停止前访问的信标数量。

样例

样例输入 #1

5
2 3 1 2 4
1 2 1 3 2

样例输出 #1

2 2 1 3 2

样例解释 #1

从 $4$ 出发，访问的信标依次是 $4,2,3$，颜色为 $3,2,1$；下一座信标 $1$ 的颜色 $1$ 已经出现，故答案是 $3$。

样例输入 #2

4
2 3 4 4
1 2 3 4

样例输出 #2

4 3 2 1

样例解释 #2

所有颜色不同。每次巡游都在准备第二次访问信标 $4$ 时停止。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$20$	$2000$	无
$2$		$2\times10^5$	A
$3$			B
$4$	$40$		无

特殊性质 A：所有 $c_i$ 两两不同。

特殊性质 B：$f_1,f_2,\ldots,f_n$ 是 $1$ 到 $n$ 的一个排列。

对于 $100\%$ 的数据，满足 $1\le n\le2\times10^5$，$1\le f_i,c_i\le n$。