解题思路

在这个问题中，我们可以注意到，当计算第 $i$ 个孩子的答案时，我们实际上也同时计算了孩子 $p_i$、$p_{p_i}$ 等孩子的答案。因此，我们可以对简单版的伪代码稍作修改，以更快地计算答案： 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 当然，我们不需要对已经计算过答案的元素重复运行这个循环。总时间复杂度为 $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;
}