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

InnitTimmer_ · 2025-11-09 20:26:43 · 题解

首先看到这个题，一眼想到的就是模拟，但是后来发现 k 太大了，完全不能模拟，所以考虑倍增。

设 fa_{i,j} 表示编号为 i 的人传 2^j 次球后会到谁手里，仿照倍增求 LCA 的思路，显然有 fa_{i,j}=fa_{fa{i,j-1},j-1}。

那我们就可以预处理出这个东西，然后直接给这个人加上答案即可，时间复杂度 O(n\times \log k)。

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
bool Test_MLE_start;
constexpr int N=1e5+10;
int _=1,n,k,ans=0,a[N],cnt[N],fa[N][31];
inline int reads(){
    int c=getchar(),x=0,f=1;
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
    return x*f;
}inline void files(){
    freopen("std.in","r",stdin);
    freopen("std.out","w",stdout);
}inline void clr(){
//  Don't forget!

}bool Test_MLE_end;
signed main(){
//  printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//  files();
//  _=reads();
    while(_--){
        clr();n=reads(),k=reads();
        for(int i=1;i<=n;i++) a[i]=reads();
        for(int i=1;i<=n;i++) fa[i][0]=reads();
        for(int j=1;j<=30;j++){
            for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1];
        }
        for(int i=1;i<=n;i++){
            int u=i,p=k;
            for(int j=30;j>=0;j--){
                int x=(1<<j);
                if(p>=x) u=fa[u][j],p-=x;
            }
            cnt[u]+=a[i];
        }for(int i=1;i<=n;i++) ans=max(ans,cnt[i]);
        printf("%lld\n",ans);
        for(int i=1;i<=n;i++){
            if(cnt[i]==ans) printf("%lld ",i);
        }
    }return 0;
}