P14467 [COCI 2025/2026 #1] 扔球 / Krugomet
Nostopathy
·
·
题解
题意
有 n 个点，每个点权值为 a_i，与 s_i 有一条单向边。进行 k 次操作，每次每个点的权值都移动到 s_i。问最后哪些点权值最大。
分析
时间复杂度 $\Theta(n \log k)$。
## 代码
```cpp
#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<<" ";
}
```
## 结语
这个游戏一定很好玩。