很深刻的题。

图上行走问题自然想到倍增，先简单尝试一下。

记 $f_{i,j,k}$ 表示日期 $\bmod T_i=k$，从 $i$ 走 $2^j$ 步到的节点。

但发现走 $2^j$ 步的过程中，可能走到 $T_u\gt T_i$ 的点，这样只记录日期 $\bmod T_i$ 的信息就不够了。

所以如果遇到了点 $u$，我们将 $f_{i,j,k}$ 强制停止在点 $u$，需要记录 $g_{i,j,k}$ 表示实际行走的长度。

我们称 $T_i$ 相同的点为同一层的点，考虑这样对于每次询问的复杂度，每一步有 2 种可能，如果强制停止了，那么层数加 $1$，否则剩余距离减半。

记 $m=\max T_i,N=\sum T_i$，每次减半前最多爬 $\log m$ 层，一次询问的复杂度为 $O(\log m\log V)$。

但是我们预处理时同样要这样走，所以总时间复杂度为 $O(N\log^2 V\log m)$，无法通过。

发现实际上我们记录这个 $2^j$ 步并没有什么意义，因为我们可能根本走不到 $2^j$ 步就强制停止了，而这个步数的要求却使得我们有较高的复杂度。

因为只有走到了，$T_u\gt T_i$ 的点 $u$ 才会强制停止，我们干脆把 $f_{i,j,k}$ 定义为，从 $i$ 走 $2^j$ 个同一层的点后到达的点，这里同样会强制停止，但是我们的预处理的复杂度变成 $O(N(\log m+\log V))$。

再来考虑询问，我们先用 $O(\log m)$ 的复杂度爬到最高层，再用 $O(\log V)$ 的复杂度找到这一层的最后一个节点，然后层数上限减 1，总复杂度 $O(\log m(\log m+log V))$。

这样，我们以 $O(N(\log m+\log V)+Q\log m(\log m+log V))$ 的复杂度解决了本题。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=2e18;
const int N=1e5+5;
int n,q,t[N],mx;
int *c[N],*f[61][N];
ll *g[61][N];
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&t[i]);
		c[i]=new int[t[i]];
		mx=max(mx,t[i]);
		for(int j=0;j<=60;++j)f[j][i]=new int[t[i]],g[j][i]=new ll[t[i]];
	}
	for(int i=1;i<=n;++i)
		for(int j=0;j<t[i];++j)scanf("%d",&c[i][j]);
	for(int j=1;j<=mx;j<<=1){
		for(int i=1;i<=n;++i)if(t[i]==j)for(int k=0;k<j;++k){
			int x=c[i][k];ll dt=1;
			while(t[x]<j&&dt<inf){
				int y=f[60][x][k+dt&t[x]-1];
				dt+=g[60][x][k+dt&t[x]-1];
				x=y;
			}
			f[0][i][k]=x,g[0][i][k]=min(inf,dt);
		}
		for(int l=1;l<=60;++l)for(int i=1;i<=n;++i)if(t[i]==j)for(int k=0;k<j;++k){
			int x=f[l-1][i][k];ll dt=g[l-1][i][k];
			if(t[x]!=j){
				f[l][i][k]=x;
				g[l][i][k]=dt;
				continue;
			}
			f[l][i][k]=f[l-1][x][k+dt&j-1];
			g[l][i][k]=min(inf,g[l-1][x][k+dt&j-1]+dt);
		}
	}
	while(q--){
		int x;ll T,dt,w;
		scanf("%d%lld%lld",&x,&T,&dt);
		while(dt){
			for(int j=60;~j&&dt;--j)if((w=g[j][x][T&t[x]-1])<=dt){
				dt-=w;
				int ls=t[x];
				x=f[j][x][T&t[x]-1];
				T+=w;
				if(t[x]!=ls)j=61;
			}
			if(dt){
				x=c[x][T&t[x]-1];
				++T,--dt;
			}
		}
		printf("%d\n",x);
	}
	return 0;
}

Problem Link

题目大意

给定 $n$ 个点的图，时刻 $t$ 在 $u$ 节点，那么 $t+1$ 时刻会在 $b_{a,t\bmod a_u}$ 节点，其中 $a_u$ 是 $2$ 的幂。

$q$ 次询问 $t$ 时刻从 $u$ 出发走 $d$ 步会到达哪个节点。

数据范围：$n,\sum a_u\le 10^5,d\le 10^{18}$。

思路分析

首先肯定需要倍增，$f_{u,t,i}$ 表示 $t$ 时刻从 $u$ 出发走 $2^i$ 步的结果，但问题是如果路程中遇到 $a_v>a_u$ 的点，$t$ 的信息就不够了。

但我们发现此时直接切换到 $v$ 的位置开始倍增，那么这个过程只会进行 $\mathcal O(\log A)$ 次，因为 $a_v\ge 2a_u$。

因此 $f_{u,t,i}$ 表示从 $u$ 出发走 $2^i$ 步或到达 $a_v>a_u$ 点的结果，$d_{u,t,i}$ 表示实际运动的步数。

那么查询复杂度 $\mathcal O(\log A\log T)$，但预处理时需要 $\mathcal O(n\log T)$ 次询问，难以接受。

注意到我们的瓶颈时 $f_{u,t,i-1}$ 可能跳到一个 $a_v<a_u$ 的点，那么就会失去 $t$ 的信息。

那么我们不妨改变定义，直接令 $f_{u,t,i}$ 表示经过 $2^i$ 个 $a_v=a_u$ 的点，或遇到 $a_v>a_u$ 的点时停止。

那么询问时我们会用 $\mathcal O(\log A)$ 轮倍增到达 $a$ 最大的点，随后每轮倍增，剩余路径上 $a$ 的最大值减小，因此倍增总轮数 $\mathcal O(\log A)$。

时间复杂度 $\mathcal O(n\log T+q\log A\log T)$。

**代码呈现 **

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+5;
const ll inf=2e18;
int n,q,a[MAXN];
vector <int> b[MAXN],f[MAXN][64];
vector <ll> d[MAXN][64];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;++i) cin>>a[i];
	for(int i=1;i<=n;++i) {
		b[i].resize(a[i]);
		for(int &p:b[i]) cin>>p;
		for(int k=0;k<=60;++k) d[i][k].resize(a[i]),f[i][k].resize(a[i]);
	}
	for(int s=1;s<MAXN;s<<=1) {
		for(int u=1;u<=n;++u) if(a[u]==s) {
			for(int i=0;i<s;++i) {
				int v=b[u][i]; ll t=1;
				while(a[v]<s&&t<inf) {
					int w=f[v][60][(i+t)%a[v]];
					t+=d[v][60][(i+t)%a[v]],v=w;
				}
				f[u][0][i]=v,d[u][0][i]=min(t,inf);
			}
		}
		for(int k=1;k<=60;++k) for(int u=1;u<=n;++u) if(a[u]==s) {
			for(int i=0;i<s;++i) {
				int v=f[u][k-1][i]; ll t=d[u][k-1][i];
				if(a[v]==s) {
					f[u][k][i]=f[v][k-1][(i+t)%s];
					d[u][k][i]=min(d[v][k-1][(i+t)%s]+t,inf);
				} else f[u][k][i]=v,d[u][k][i]=t;
			}
		}
	}
	for(int u;q--;) {
		ll dis,cur;
		cin>>u>>cur>>dis;
		while(dis) {
			for(int k=60;~k;--k) if(dis>=d[u][k][cur%a[u]]) {
				int v=f[u][k][cur%a[u]];
				ll t=d[u][k][cur%a[u]];
				if(a[v]!=a[u]) k=61;
				dis-=t,cur+=t,u=v;
			}
			if(dis) u=b[u][cur%a[u]],--dis,++cur;
		}
		cout<<u<<"\n";
	}
	return 0;
}