我们发现，这张图一定是若干个环，环上节点可能连接着一棵树。那么不妨去考虑每一个点跳到环上时对应的点，然后再动整个环，这样就做完了。

但真的这么简单吗？

我们定义一个节点 $x$ 到环的距离为 $dep_x$，那么令 $k<\max_{1\le i\le n}(dep_i)$，此时，对于 $dep_x>k$ 的 $x$，我们就需要考虑上跳 $k$ 步后落在哪里，显然无法暴力跳（毕竟有个东西叫链套菊花），所以问题就转变为如何快速求树上所有节点的 $k$ 级祖先，这个问题显然可以用 st 表解决。

我们再想：既然刚刚那个问题可以用 st 表，st 表又能在 $O(n\log k)$ 的复杂度内求出每一个数跳 $k$ 次后的结果，这里还满足每一个点跳 $k$ 次的路径是唯一的。那么我们就可以抛弃原本的所有想法，直接用 st 表解决原问题，时间复杂度 $O(n\log k)$。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int ed[100005];
int ans[100005];
int st[100005][32];
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ed[i]=i;
	}
	for(int i=1;i<=n;i++){
		cin>>st[i][0];
	}
	for(int i=1;i<=30;i++){
		for(int j=1;j<=n;j++){
			st[j][i]=st[st[j][i-1]][i-1];
		}
	}
	for(int i=30;i>=0;i--){
		for(int j=1;j<=n;j++){
			if(k>=(1<<i)){
				ed[j]=st[ed[j]][i];
				k-=(1<<i);
			}
		}
	}
	int mx=0;
	for(int i=1;i<=n;i++){
		ans[ed[i]]+=a[i];
	}
	for(int i=1;i<=n;i++){
		mx=max(mx,ans[i]);
	}
	cout<<mx<<"\n";
	for(int i=1;i<=n;i++){
		if(ans[i]==mx){
			cout<<i<<" ";
		}
	}
	return 0;
}

题意

有 $n$ 个点，每个点权值为 $a_i$，与 $s_i$ 有一条单向边。进行 $k$ 次操作，每次每个点的权值都移动到 $s_i$。问最后哪些点权值最大。

分析

$k$ 的范围很大，考虑优化到 $\log$。定义 $st_{i,j}$ 表示第 $i$ 个节点进行 $2^j$ 轮操作后，他的权值移动到了哪个点，转移是 $st_{i,j}=st_{st_{i,j-1},j-1}$。然后遍历每个点，将操作次数拆分，找到最终传给了哪个节点。

时间复杂度 $\Theta(n \log k)$。

代码

#include<bits/stdc++.h>
using namespace std;
using LL=long long int;
const int N=1e5+5;
int n,k,a[N],cnt[N],st[N][35];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1,crush;i<=n;++i)cin>>crush,st[i][0]=crush;
    int m=__lg(k);
    for(int j=1;j<=m;++j)for(int i=1;i<=n;++i)st[i][j]=st[st[i][j-1]][j-1];
    for(int i=1;i<=n;++i){
        int num=i,now=m,round=k;
        while(round){
            if(round>=(1<<now))round-=(1<<now),num=st[num][now];
            --now;
        }
        cnt[num]+=a[i];
    }
    int mx=0;
    for(int i=1;i<=n;++i)mx=max(mx,cnt[i]);
    cout<<mx<<"\n";
    for(int i=1;i<=n;++i)if(cnt[i]==mx)cout<<i<<" ";
}

结语

这个游戏一定很好玩。