CF2008D.Sakurako's Hobby

对于一个给定的排列 $ p $，Sakurako 称整数 $ j $ 从整数 $ i $ 可达，意思是可以通过若干次操作将 $ i $ 改为 $ p_i $，最终使 $ i $ 等于 $ j $。

举个例子，如果 $ p=[3,5,6,1,2,4] $，那么 $ 4 $ 是从 $ 1 $ 可达的，因为变化过程可以是：$ i=1 \rightarrow i=p_1=3 \rightarrow i=p_3=6 \rightarrow i=p_6=4 $。这样 $ i $ 就变成了 $ 4 $，因此 $ 4 $ 是从 $ 1 $ 可达的。

在这个排列中，每个数字都有两种颜色：黑色或白色。

Sakurako 定义了一个函数 $ F(i) $，表示从 $ i $ 可达的黑色整数的总数。

她对每一个 $ 1\le i\le n $ 的 $ F(i) $ 都很感兴趣，但计算所有值太过复杂，因此她希望你能帮助她解决这个问题。

一个长度为 $ n $ 的排列是一个由 $ 1 $ 到 $ n $ 这 $ n $ 个不同整数构成的数组。例如，$ [2,3,1,5,4] $ 是一个排列，而 $ [1,2,2] $ 却不是（因为数字 $ 2 $ 出现了两次），同样地，$ [1,3,4] $ 也不是（$ n=3 $，但数组中包含 $ 4 $）。

第一行输入一个整数 $ t $（$ 1\le t\le 10^4 $），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $ n $（$ 1\le n\le 2\cdot 10^5 $），表示数组中元素的数量。

接下来的每一行包含 $ n $ 个整数 $ p_1, p_2, \dots, p_n $（$ 1\le p_i\le n $），表示排列的具体内容。

随后的一行包含一个由字符 '0' 和 '1' 组成的长度为 $ n $ 的字符串 $ s $。如果 $ s_i=0 $，则表示数字 $ p_i $ 是黑色；如果 $ s_i=1 $，则表示数字 $ p_i $ 是白色。

保证所有测试用例之中 $ n $ 的总和不超过 $ 2\cdot 10^5 $。

对于每个测试用例，输出 $ n $ 个整数 $ F(1), F(2), \dots, F(n) $。

本翻译由 AI 自动生成