算起来复杂度大概是mlogn左右，但真的一直TLE，真的想不通怎么T掉的，只A了前两个点

蒟蒻求助

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <cmath>
using namespace std;
const long long MAXN=4e5+5,MAXM=3e5+5;
long long n,a[MAXN][35],m,S,t1,t2,lgn;
bool Vis[MAXN]={0};
long long To[MAXN],Start[MAXN],Len,Tmp,In[MAXN]={0},Ring[MAXN],Index[MAXN],From[MAXN]={0};//a[i][0]µ¥¶À¿¼ÂÇ RingΪ0_Len-1µÄϱ귶Χ 
void getTo(long long Now){//Right ÓÃÀ´Ñ°ÕÒ±¶Ôö£¬²»ÔÚ»·ÉϵĵãλÖõÄËÑË÷ O(n)
	long long Begin=Now;
	while(Vis[Now]==false){ 
		//cout<<"Now::"<<Now<<endl;
		From[a[Now][0]]=Now;
		Vis[Now]=true;
		Now=a[Now][0];
	}
	while(true){
		for(register long long i=1;a[a[Now][i-1]][i-1]!=0&&i<=lgn;++i){
			//cout<<"Now::"<<Now<<endl;
			a[Now][i]=a[a[Now][i-1]][i-1];
		}
		To[Now]=To[a[Now][0]]+1;
		Start[Now]=Start[a[Now][0]];
		if(Now==Begin||From[Now]==0)break;
		Now=From[Now];
	}
}
void getRing(){//Right Ñ°ÕÒ»·µÄ³¤¶È£¬²¢±ê¼Ç O(n)
	bitset<MAXN> been;
	long long Now=1,Origin;
	while(true){
		if(been[Now]==1)break;
		been[Now]=1;
		Now=a[Now][0];
	}
	Origin=Now;long long tmp=0;
	Len=0;
	while(true){
		if(Now==Origin)++tmp;if(tmp==2)break;
		Ring[Len]=Now;Index[Now]=Len;Vis[Now]=true;
		//cout<<"la::"<<Index[Now]<<" "<<Now<<endl;
		++Len;
		To[Now]=0;Start[Now]=Now;
		Now=a[Now][0];
	}
	for(register long long i=1;i<=n;++i)
		if(In[i]==0)
			getTo(i);
}
long long ModPow(long long t1,long long t2,long long Mod){//Right Çót1^t2%Mod O(log2 t2)
	if(t2==0)return 1;
	long long tmp=t1%Mod,Ans=1;
	while(t2!=0){
		if(t2&1)Ans=(tmp*Ans)%Mod;
		tmp=(tmp*tmp)%Mod;
		t2>>=1;
	}
	return Ans%Mod;
}
long long Find(long long Now,long long Go){//Right Ñ°ÕÒNowÏòÇ°Go¸öλÖõÄϱê O(log2 Go)
	long long Sum=0;
	while(Go!=0){
		if(Go&1)Now=a[Now][Sum];
		++Sum;
		Go>>=1;
	} 
	return Now;
}
int main(){
	scanf("%lld",&n);
	lgn=log(n)/log(2)+1e-7;
	for(register long long i=1;i<=n;++i)
		scanf("%lld",&a[i][0]),++In[a[i][0]];
	for(register long long i=0;i<=n;++i)
		To[i]=-1,Start[i]=0;
	getRing();
//	cout<<"To&Start::"<<endl;
//	for(register long long i=1;i<=n;++i)	
//		cout<<To[i]<<" "<<Start[i]<<endl;
//	cout<<"Len::"<<Len<<endl;
//	cout<<"a[i][j]::"<<endl;
//	for(register long long i=1;i<=n;++i){
//		for(register long long j=0;j<=32;++j){
//			if(a[i][j]==0){
//				cout<<0<<endl;
//				break;
//			}
//			cout<<a[i][j]<<" ";
//		}
//	}
//	cout<<"Ring::"<<endl;
//	for(register long long i=0;i<Len;++i)
//		cout<<Ring[i]<<" ";
//	cout<<endl;
	scanf("%lld",&m); 
	long long Ans,tmp1;
	for(register long long i=1;i<=m;++i){
		scanf("%lld%lld%lld",&S,&t1,&t2);
		//O(m*log2 t2)
		if(To[S]==0){
			Tmp=ModPow(t1,t2,Len);
			if(Index[Start[S]]+Tmp>=Len)Tmp-=Len;
			if(Index[Start[S]]+Tmp<0)Tmp+=Len;
			Ans=Ring[Index[Start[S]]+Tmp];
		}
		else if(t2<=log((double)To[S])/log((double)t1)){
			Ans=Find(S,ModPow(t1,t2,MAXN));
		}else{
			Tmp=ModPow(t1,t2,Len);
			tmp1=To[S]%Len;
			if(Index[Start[S]]+Tmp-tmp1>=Len)Tmp-=Len;
			if(Index[Start[S]]+Tmp-tmp1<0)Tmp+=Len;
			//cout<<" "<<Index[S]+Tmp-tmp1<<endl;
			Ans=Ring[Index[Start[S]]+Tmp-tmp1];
		}
		printf("%lld\n",Ans);
	}
	return 0;
}
/*
10
2 3 1 1 4 5 6 7 8 9
7
8 3 1
10 5 1
10 2 2
4 2 4
4 3 1
4 2 1
4 1 1


5 5 6 1 3 2 1
*/
/*
11
2 3 4 1 1 5 6 2 8 8 10
5
11 4 2
7 2 1
9 3 2
9 128 1000000000
2 3 2

3 5 1 ~ 3
*/