9526 2024. 02. 22 14:46:02 Vkrisztian01 Tevefarm cpp17 Elfogadva 50/50 101ms 15028 KiB
#include <iostream>
#include<vector>

using namespace std;


int n,a,b;
vector<vector<int> > g;
vector<long long int>label;
vector<long long int>dp;
vector<bool>valasztom;
vector<int>ki;

void dfs(int node)
{
    long long int osszeg=0;
    for(auto to:g[node])
    {
        dfs(to);
        osszeg+=dp[to];
    }
    dp[node]=max(label[node],osszeg);
    if(label[node]>osszeg) valasztom[node]=true;
    else valasztom[node]=false;
}

void bejar(int node)
{
    if(valasztom[node])
    {
        ki.push_back(node);
        return;
    }
    for(auto to:g[node]) bejar(to);
}

int main()
{
    cin>>n;
    g.resize(n+1);
    dp.assign(n+1,0);
    valasztom.resize(n+1);
    label.resize(n+1);
    for(int i=1;i<=n;i++) cin>>label[i];
    for(int i=2;i<=n;i++)
    {
        cin>>a;
        g[a].push_back(i);
    }
    dfs(1);
    cout<<dp[1]<<endl;
    bejar(1);
    cout<<ki.size()<<endl;
    for(auto x:ki) cout<<x<<" ";
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1756 KiB
2 Elfogadva 0/0 3ms 2096 KiB
3 Elfogadva 4/4 3ms 2124 KiB
4 Elfogadva 4/4 3ms 2380 KiB
5 Elfogadva 4/4 3ms 2576 KiB
6 Elfogadva 4/4 3ms 2948 KiB
7 Elfogadva 4/4 43ms 8984 KiB
8 Elfogadva 6/6 52ms 10124 KiB
9 Elfogadva 6/6 61ms 11752 KiB
10 Elfogadva 6/6 68ms 12780 KiB
11 Elfogadva 6/6 92ms 13968 KiB
12 Elfogadva 6/6 101ms 15028 KiB