Codeforces_forever Round #1 (Div3) B2

//решение
В этой задаче мы можем заметить, что когда мы считаем ответ для ребенка i, мы также считаем ответ для детей pi, ppi и так далее. Таким образом, мы можем немного модифицировать псевдокод из простой версии, чтобы считать ответы быстрее:


pos = p[i]
ans = 1
cycle = [i]
while pos != i:
    cycle.append(pos)
    ans += 1
    pos = p[pos]
for el in cycle: res[el] = ans
И, конечно же, нет необходимости запускать этот while для всех элементов, для которых мы уже посчитали ответ. Асимптотика решения — O(n), потому что вы обработаете каждый элемент единожды.
//реализация
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int n;
		cin >> n;
		vector<int> p(n);
		for (int j = 0; j < n; ++j) {
			cin >> p[j];
			--p[j];
		}
		vector<int> used(n);
		vector<int> ans(n);
		for (int j = 0; j < n; ++j) {
			if (!used[j]) {
				vector<int> cur;
				while (!used[j]) {
					cur.push_back(j);
					used[j] = true;
					j = p[j];
				}
				for (auto el : cur) ans[el] = cur.size();
			}
		}
		for (int j = 0; j < n; ++j) cout << ans[j] << " ";
		cout << endl;
	}

	return 0;
}