题解：P14467 [COCI 2025/2026 #1] 扔球 / Krugomet

· · 题解

首先，暴力的复杂度为 O(nk)，只能获得 14pts。

考虑为什么暴力抛这么慢。原因是暴力抛一个一个抛，太慢了，应该一段一段抛。

一段一段跳，就可以想到倍增，记 p_{u,j} 为 u 开始抛 2^j 次抵达的位置，转移显然：p_{u,j}=p_{p_{u,j-1},j-1}。

然后最后求 u 抛 k 次的结果跟倍增求 k 级祖先是类似的，就是“抵挡诱惑”，只有当 k \ge 2^p 时再跳 2^p 步，代码很简单，二十多行。

#include<bits/stdc++.h>
using namespace std;
const int N=100009;
int p[N][32],a[N],s[N],ans[N],n,k,L;
int go(int x,int y){
    int u=x;
    for(int i=30;i>=0;i--)
        if(y>=(1<<i)) y-=(1<<i),u=p[u][i];
    return u;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>s[i],p[i][0]=s[i];
    L=log2(k);
    for(int j=1;j<=L;j++)
        for(int u=1;u<=n;u++)
            p[u][j]=p[p[u][j-1]][j-1];
    for(int i=1;i<=n;i++) ans[go(i,k)]+=a[i];
    int mx=0;
    for(int i=1;i<=n;i++) mx=max(mx,ans[i]);
    cout<<mx<<endl;
    for(int i=1;i<=n;i++)
        if(ans[i]==mx) cout<<i<<" ";
    cout<<endl;
    return 0;
}