求助,大样例#2本地RE(把小电脑都卡爆了),评测100
  • 板块P12734 理解
  • 楼主zhouyoyo
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/6/28 21:37
  • 上次更新2025/6/29 15:52:37
查看原帖
求助,大样例#2本地RE(把小电脑都卡爆了),评测100
724190
zhouyoyo楼主2025/6/28 21:37
#include <iostream>
#include <vector>
using namespace std;
#define int long long
const int NR=1e5+5;
int T,n,m,k,p[NR],r[NR],t[NR],x[NR],F[NR],f[NR][11],g[NR][11],sum[11];
bool exam[NR];
vector<int>e[NR];
void Dfs(int u){
	for(int i=0;i<=k;i++)f[u][i]=0;
    for(int v:e[u])
        Dfs(v);
    F[u]=0;
    if(!exam[u])
        for(int v:e[u])
            F[u]+=min(F[v],f[v][k-1]+r[v]);
    else
        F[u]=1e18;
    for(int i=0;i<=k;i++)sum[i]=f[u][i]=0;
    for(int v:e[u]){
    	f[u][0]+=min(F[v],f[v][k-1]+r[v]);
    }
    for(int v:e[u])
        for(int i=1;i<=k;i++){
            g[v][i]=min(F[v],min(f[v][k-1]+r[v],f[v][i-1]+t[v]));  
            f[u][i]+=g[v][i];
            sum[i]+=g[v][i];
        }
    for(int v:e[u]){
        for(int i=1;i<=k;i++){
            int H=sum[i]-g[v][i]+f[v][i]+t[v];
            f[u][i]=min(f[u][i],H);
        }
    }
}
signed main(){
    cin>>T;
    while(T--){
        cin>>n>>m>>k;
    	for(int i=0;i<=n;i++)e[i].clear();
        for(int i=1;i<=n;i++)exam[i]=0;
        for(int i=1;i<=n;i++)cin>>p[i];
        for(int i=1;i<=n;i++)e[p[i]].push_back(i);
        for(int i=1;i<=n;i++)cin>>r[i];
        for(int i=1;i<=n;i++)cin>>t[i];
        for(int i=1;i<=m;i++)cin>>x[i];
        for(int i=1;i<=m;i++)exam[x[i]]=1;
        Dfs(0);
        cout<<F[0]<<'\n';
    }
    return 0;
}

2025/6/28 21:37
加载中...