ACM-ICPC-OJ训练营

问题 K: 整点图论

时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 7
[提交][状态][讨论版][命题人:]

题目描述

对于某个排列 p如果可以通过赋值 i=p_i一定次数使 i 等于 j，则樱子称整数 j 可以从整数 i 到达。

如果是 p=[3,5,6,1,2,4] ，那么，举例来说， 4可以从 1 到达，因为： i=1→i=p₁=3 i=p₃=6 i=p₆=4 .现在是 i=4，所以从 1可以到达 4。

排列中的每个数字都被染成黑色或白色。

樱子将函数 F(i)定义为从可以到达的黑色整数的个数。

樱子对每个 1≤i≤n的 F(i)都很感兴趣，但是计算所有值变得非常困难，所以她请你作为她的好朋友来计算一下。

第一行包含一个整数 t( 1≤t≤10000 ) - 测试用例数。

每个测试用例的第一行包含一个整数 n( 1≤n≤200000 ) - 数组中的元素个数。

每个测试用例的第二行包含 n个整数 p1,p2,…,pn( 1≤pi≤n ) - 排列元素。

每个测试用例的第三行包含一个长度为的字符串 s ，由 "0 "和 "1 "组成。如果是 si=0，那么数字 pi的颜色为黑色；如果是 si=1，那么数字 pi的颜色为白色。

保证所有测试用例中 n的总和不超过 200000 。

对于每个测试用例，输出 n 个整数

F(1),F(2),…,F(n)。

5
1
1
0
5
1 2 4 5 3
10101
5
5 4 1 3 2
10011
6
3 5 6 1 2 4
010000
6
1 2 3 4 5 6
100110

1 
0 1 1 1 1 
2 2 2 2 2 
4 1 4 4 1 4 
0 1 1 0 0 1