Олимпиадный тренинг

Задача . D. Хобби Сакурако

Задача

Для некоторой перестановки \(p\)\(^{\text{∗}}\) Сакурако называет целое число \(j\) достижимым из целого числа \(i\), если можно сделать так, чтобы \(i\) стало равным \(j\), присваивая \(i=p_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\).

Сакурако интересует \(F(i)\) для каждого \(1\le i\le n\), но вычислить все значения становится очень сложно, поэтому она просит вас, как своего хорошего друга, вычислить это.

\(^{\text{∗}}\)Перестановка длины \(n\) — это массив, состоящий из \(n\) различных целых чисел от \(1\) до \(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\)) — элементы перестановки.

Третья строка каждого набора содержит строку \(s\) длины \(n\), состоящую из '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)\).

Примеры

№	Входные данные	Выходные данные
1	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

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет