参考题解：https://blog.csdn.net/weixin_51937688/article/details/119577657
自己动手写几个样例就会发现 g(x)的值跟每个环的平均值有关
若每个环的平均值相同 则g(x)的值也都会相同
分为两个部分:
第一步:找环 第二步：求平均值

#include <bits/stdc++.h>
#define pb push_back
#define xx first
#define yy second
#define in(x) scanf("%d",&x)
#define lin(x) scanf("%lld",&x)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e6+10;
const int M = N*2;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
const double PI = acos(-1);
ll qpow(ll a,ll b){ll res = 1;while(b){if(b&1)  res = res*a%MOD;a = a*a%MOD;b >>= 1;}return res;}
ll n,an;   // an 判断是 YES 还是 NO
bool loop[N];
double sum = 0,ans = 0;
ll f[N],ff[N];   // f 又是路径 也是 值  ff 前缀和
int vis[N];
vector <int> f2[N];

void dfs2(int x){   // 遍历反向边
    if(loop[x]) return;

    loop[x] = 1;
    for(auto e : f2[x]) dfs2(e);
}

void dfs(int x,ll cnt){ // cnt 记录环的大小
    if(!an) return; // 剪枝

    ff[x] = sum;
    sum += f[x];
    vis[x] = cnt;

    if(!vis[f[x]])  dfs(f[x],cnt+1);
    else{   // 下一个已经访问过了 说明成环了
        dfs2(x);    // 标记 环 接出去的分支

        int s = cnt - vis[f[x]] + 1;    // 对环有贡献的节点总数
        if(!s)  return;
        sum = (ff[x] + f[x] - ff[f[x]])*1.0/s;  // 平均值

        if(!ans)    ans = sum;  // 如果是第一个环 则将其平均值作为标准
        if(ans != sum)  an = 0; // 如果平均值与标准不相同 则说明不能得出答案
    }
    return;
}

void init(){
    memset(f,0,sizeof(f[0])*(n+1));
    memset(loop,0,sizeof(loop[0])*(n+1));
    memset(ff,0,sizeof(ff[0])*(n+1));
    memset(vis,0,sizeof(vis[0])*(n+1));
    for(int i=1;i<=n;i++)   f2[i].clear();
    an = 1,ans = sum = 0;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
#endif
    int T;  in(T);
    while(T--){
        in(n);
        init();

        for(int i = 1;i <= n;i++){
            in(f[i]);
            f2[f[i]].pb(i);
        }

        for(int i = 1;i <= n;i++){
            if(!loop[i]){
                sum = 0;
                dfs(i,1);
            }
        }

        puts(an?"YES":"NO");
    }
    return 0;
}