152062025-02-16 18:19:55antiTevefarmcpp17Időlimit túllépés 16/50600ms7336 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
//#include <fstream>

using namespace std;

vector<vector<int>> children;
vector<long long> L[2];

void dfs( int u, const vector<long long>& T ){
    L[0][u] = 0;
    L[1][u] = T[u];
    for(int v : children[u]){
        dfs( v, T);
        L[0][u] += max( L[0][v], L[1][v] );
    }
}

int main(){
    //ifstream fin("be2.txt");
    int n;
    cin >> n;

    vector<long long> T(n);
    for(int i=0; i<n; i++){
        cin >> T[i];
    }

    children.resize(n);
    int h[n];
    for(int i=1; i<n; i++){
        int parent;
        cin >> parent;
        h[i] = parent;
        h[i]--;
        children[parent - 1].push_back(i);
    }
    L[0].assign(n, 0);
    L[1].assign(n, 0);

    dfs( 0, T );
    long long max_sum = max(L[0][0], L[1][0]);
    cout << max_sum << endl;

    vector<int> selected;
    int v[n] = {0};
    stack<int> s;
    s.push(0);
    v[0] = 1;
    while(!s.empty()){
        int x = s.top();
        s.pop();

        if(L[0][x] < L[1][x]){
            selected.push_back(x+1);
            for(int i : children[x]){
                v[i] = 1;
            }
        }

        for(int y=1; y<n; y++){
            if(h[y] == x && v[y] == 0){
                s.push(y);
            }
        }
    }
    cout << selected.size() << endl;
    for(int i=0; i<selected.size(); i++){
        cout << selected[i] << " ";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base16/50
1Elfogadva0/01ms500 KiB
2Elfogadva0/02ms512 KiB
3Elfogadva4/41ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/41ms436 KiB
6Elfogadva4/42ms472 KiB
7Időlimit túllépés0/4600ms3880 KiB
8Időlimit túllépés0/6600ms4704 KiB
9Időlimit túllépés0/6600ms5204 KiB
10Időlimit túllépés0/6600ms6112 KiB
11Időlimit túllépés0/6575ms6764 KiB
12Időlimit túllépés0/6575ms7336 KiB