连接 $i\to p_i$ 边。图只有环。

:::success[为什么]{open} $p$ 为排列，所以图上只存在置换环。 :::

对于每个环 $C=\{i,p_i,p_{p_i},\cdots\}$，

• 如果长度 $\ge k+1$ 则所有服务都能转移到某个点上，答案为 $\sum_Ca$。
• 否则断环为链，将环数组复制一份到 $C$ 后，能转移到的服务为长度为 $k+1$ 的区间和。对于所有区间和取 $\max$。区间和使用前缀和做。

我这个实现不是很好，用了并查集，不过其实不用。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
int a[maxn],p[maxn],f[maxn],pre[maxn*2],n,k;
void init(){
    for(int i=1;i<maxn;i++)f[i]=i;
}
int find(int x){
    if(f[x]==x)return f[x];
    return f[x]=find(f[x]);
}
void merge(int x,int y){
    f[find(x)]=find(y);
}
vector<int> T[maxn],q;
bitset<maxn> v;
void dfs(int u){
    if(v[u])return;
    v[u]=1;
    // cout<<u<<' '<<dep<<endl;
    q.push_back(a[u]);
    dfs(p[u]);
    // cout<<u<<' '<<ans+a[u]<<endl;
}
int work(){
    int vize=q.size();
    if(vize<=k+1){
        int sum=0;
        for(auto i:q)sum+=i;
        return sum;
    }
    for(int i=0;i<vize;i++)q.push_back(q[i]);
    // for(auto i:q)cout<<i<<' ';
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=q.size();i++){
        pre[i]=pre[i-1]+q[i-1];
        // cout<<pre[i]<<' ';
    }
    // cout<<endl;
    int l=1,r=k+1,ans=0;
    while(l<=v.size()){
        // cout<<l<<' '<<r<<endl;
        ans=max(ans,pre[r]-pre[l-1]);
        // cout<<pre[r]-pre[l-1]<<' '<<pre[r]<<' '<<pre[l-1]<<' '<<l-1<<endl;
        l++,r++;
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    // freopen("sect.in","r",stdin);
    // freopen("sect.out","w",stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    init();
    for(int i=1;i<=n;i++){
        cin>>p[i];
        T[i].push_back(p[i]);//
        merge(p[i],i);
    }
    //每个连通块是环
    int ans=0;
    for(int i=1;i<=n;i++){
        if(f[i]!=i)continue;
        v.reset();
        // cout<<i<<endl;
        q.clear();
        dfs(i);
        ans=max(ans,work());
    }
    cout<<ans;
    return 0;
}

:::

赛时没看到是排列，只看到 $1\le p_i\le n$，差点写出诡异基环树 DP。