146942025-01-28 08:43:48csdavidTevefarmcpp17Elfogadva 50/50111ms9012 KiB
#include <iostream>
#include <vector>
#include <queue>
//#include <fstream>
using namespace std;
//#define cin fin
struct node{
    long long dp=0, teve;
    bool bejart=0, kivalaszt=0, megoldas=0;
    vector<long long> gyerek;
    long long szulo, done=0;
};

int main()
{
    //ifstream fin("be2.txt");
    long long n, x, y;
    cin >> n;
    node a[n];
    for(long long i=0; i<n; i++){
        cin >> a[i].teve;
        //a[i].dp=a[i].teve;
    }
    a[0].szulo=-1;
    for(long long i=1; i<n; i++){
        cin >> x;
        a[i].szulo=x-1;
        a[x-1].gyerek.push_back(i);
    }
    queue<long long> q;
    for(long long i=0; i<n; i++){
        if(!a[i].gyerek.size()){
            q.push(i);
            a[i].bejart=1;
        }
    }
    /*for(long long i=0; i<n; i++){
        cout << i << ": ";
        for(auto& it:a[i].gyerek){
            cout << it << ' ';
        }
        cout << '\n';
    }
    cout << "\n\n";*/
    bool jo;
    while(!q.empty()){
            jo=1;
        x=q.front();
        q.pop();
        a[x].dp=0;
        //cout << x << ": ";
        for(auto& it:a[x].gyerek){
            if(a[x].dp==0){
                jo=0;
            }
            a[x].dp+=a[it].dp;
            //cout << '|' << it << ": ";
            //cout << a[it].dp << '|';
        }
       // cout << "\n" << a[x].dp << "\\" << a[x].teve;
        if(a[x].teve>a[x].dp){
            a[x].dp=a[x].teve;
            a[x].kivalaszt=1;
            /*if(a[a[x].szulo].bejart==0){
                q.push(a[x].szulo);
                a[a[x].szulo].bejart=1;
            }*/
        }
        /*else if(a[a[x].szulo].bejart==0){
            q.push(a[x].szulo);
            a[a[x].szulo].bejart=1;
        }*/
        if(x!=0){
            a[a[x].szulo].done++;
            if(a[a[x].szulo].done==a[a[x].szulo].gyerek.size()){
                q.push(a[x].szulo);
            }
        }
        //cout << "|||" << a[x].dp << "\n\n";
    }
    /*for(long long i=0; i<n; i++){
            cout << i+1 << ' ' << a[i].dp << '\n';
    }*/
    cout << a[0].dp << '\n';
    q.push(0);
    y=0;
    if(a[0].kivalaszt){
        a[0].megoldas=1;
        y=1;
    }
    else{
        while(!q.empty()){
            x=q.front();
            q.pop();
            for(auto& it:a[x].gyerek){
                if(a[it].kivalaszt){
                    a[it].megoldas=1;
                    y++;
                }
                else{
                    q.push(it);
                }
            }
        }
    }
    cout << y << '\n';
    for(long long i=0; i<n; i++){
        if(a[i].megoldas){
            cout << i+1 << ' ';
        }
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/02ms316 KiB
3Elfogadva4/41ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/41ms316 KiB
6Elfogadva4/42ms316 KiB
7Elfogadva4/443ms4812 KiB
8Elfogadva6/652ms5616 KiB
9Elfogadva6/664ms6536 KiB
10Elfogadva6/676ms7332 KiB
11Elfogadva6/694ms8336 KiB
12Elfogadva6/6111ms9012 KiB