记录编号	589739	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	收益	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	9.697 s
提交时间	2024-07-07 16:11:50	内存使用	134.57 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 4000010
#define ll long long
#define mod 1000000007
ll n,k,seed,idx,cnt;
ll hd[MAXN],nxt[MAXN],ed[MAXN];
ll val[MAXN],sum[MAXN];
void build(ll x,ll y){
    nxt[++idx]=hd[x];
    hd[x]=idx;
    ed[idx]=y;
}
bool cmp(ll a,ll b){
    return a>b;
}
ll dfs(ll num){
//    cout<<num<<endl;
    ll maxz=0;
    for(int i=hd[num];i;i=nxt[i]){
        ll y=ed[i];
//        cout<<"y:"<<y<<endl;
        ll s=dfs(y);
        if(s>maxz){
            if(maxz)sum[++cnt]=maxz;
            maxz=s;
        }else{
            sum[++cnt]=s;
        }
    }
    return maxz+val[num];
}
int main(){
    freopen("x.in","r",stdin);
    freopen("x.out","w",stdout);
    cin>>n>>k>>seed;
    val[1]=seed;
    for(int i=2;i<=n;i++){
        val[i]=(val[i-1]*23333333+6666666)%mod;
        build((val[i]^23333333)%(i-1)+1,i);
//        cout<<val[i]<<" "<<(val[i]^23333333)%(i-1)+1<<endl;
    }
    sum[++cnt]=dfs(1);
    ll ans=0;
    sort(sum+1,sum+1+cnt,cmp);
    for(int i=1;i<=k;i++){
        ans+=sum[i];
    }
    cout<<ans;
    return 0;
}