P14467 [COCI 2025/2026 #1] 扔球 / Krugomet 题解
题目链接
我的博客
思路
这道题，\(k\) 的取值范围很大，我们考虑倍增。
设 \(f_{i,j}\) 表示第 \(i\) 个人，经过 \(2^j\) 轮，最终扔给哪个人。然后递推式即为
\[f_{i,j}=f_{f_{i,j-1},j-1}
\]
表示含义为：第 \(i\) 个人，经过 \(2^j\) 轮扔给谁是经过 \(2^{j-1}\) 轮之后再经过 \(2^{j-1}\) 扔给谁。
时间复杂度 \(O(n \log k)\)。
代码
const int N=4e5+10;
int n,k,a[N];
ll f[N][50];//同上
ll ans[N];//答案
int findf(int x,int k){//倍增找 x 经过 k 轮后的“祖先”for(int j=31;j>=0;j--){if(k&(1<<j)){x=f[x][j];}}return x;
}
signed main(){n=Read();k=Read();for(int i=1;i<=n;i++) a[i]=Read();for(int i=1;i<=n;i++){int x=Read();f[i][0]=x;//直接“父节点”即为暗恋对象}//倍增的预处理for(int j=1;j<=31;j++){for(int i=1;i<=n;i++){f[i][j]=f[f[i][j-1]][j-1];}}for(int i=1;i<=n;i++){int fa=findf(i,k);ans[fa]+=a[i];}ll mx=0;for(int i=1;i<=n;i++){mx=max(mx,ans[i]);}printf("%lld\n",mx);for(int i=1;i<=n;i++){if(mx==ans[i]) printf("%lld ",i);}return 0;
}