题目描述

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

如果是 $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$ 到达。

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

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

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

$^{\text{∗}}$ 长度为 $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$ ) - 排列元素。

每个测试用例的第三行包含一个长度为 $n$ 的字符串 $s$ ，由 “0 “和 “1 “组成。如果 $s_i=0$ ，则数字 $p_i$ 被涂成黑色；如果 $s_i=1$ ，则数字 $p_i$ 被涂成白色。

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

对于每个测试用例，输出 $n$ 个整数 $F(1), F(2), \dots, 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 

算法1

(dfs) $O(logn)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define endl '\n'
int k[N], cnt[N];
bool bo[N]; int ds[N];
string s;


int dfs(int x)
{
    if (!bo[x])
    {
        bo[x] = 1;
        if (s[x] == '0')
        {
            cnt[x] = dfs(k[x]) + 1;
        }
        else cnt[x] = dfs(k[x]);
    }
    if (x == k[x])return 0;
    return cnt[x];
}

//先遍历所有数，查找环；
int dck(int x,int y)
{
    if (x == k[x])return -1;//不是环
    if (!ds[x])
    {
        ds[x] = 1;
        ds[x] = dck(k[x], y);
    }
    return ds[x]= y;//是环
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--)
    {
        memset(k, 0, sizeof k);
        memset(cnt, 0, sizeof cnt);
        memset(bo, 0, sizeof bo);
        memset(ds, 0, sizeof ds);
        int n; cin >> n;
        for (int i = 1; i <= n; i++)cin >> k[i];
        for (int i = 1; i <= n; i++)
        {
            if (!ds[i])dck(i, i);
        }
        //cout << "eg:";
        //for (int i = 1; i <= n; i++)cout << ds[i] <<" ";
        //cout << endl;
        cin >> s;
        s = "*" + s;
        for (int i = 1; i <= n; i++)
        {
            if (bo[i]&&ds[i] != -1 && ds[i] != 0)
            {
                cnt[i] = cnt[ds[i]];
            }
            else if(!bo[i])dfs(i);
        }
        for (int i = 1; i <= n; i++)cout << cnt[i]<<" ";
    }
    return 0;
}