155962025-02-20 20:23:22BucsMateTevefarmcpp17Elfogadva 50/50103ms6492 KiB
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void DFS(vector<vector<int>> &adj, int node, long long termeles[], long long dp[])
{
    long long sum = 0;
    for(int i = 0; i < adj[node].size(); i++){
        DFS(adj, adj[node][i], termeles, dp);
        sum += dp[adj[node][i]];
    }
    dp[node] = max(termeles[node], sum);
}

long long BFS(vector<vector<int>> &adj, long long termeles[], long long dp[], vector<int> &megoldas)
{
    long long osszeg = 0;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int currNode = q.front();
        q.pop();
        if(dp[currNode] == termeles[currNode]){
            osszeg += dp[currNode];
            megoldas.push_back(currNode);
            continue;
        }
        for(int i = 0; i < adj[currNode].size(); i++){
            int newNode = adj[currNode][i];
            q.push(newNode);
        }
    }
    return osszeg;
}

int main()
{
    int N;
    cin >> N;
    vector<vector<int>> adj(N+1);
    long long termeles[100001];
    for(int i = 1; i <= N; i++){
        cin >> termeles[i];
    }
    for(int i = 2; i <= N; i++){
        int a;
        cin >> a;
        adj[a].push_back(i);
    }

    long long dp[100001] = {};
    DFS(adj, 1, termeles, dp);
    vector<int> megoldas;
    cout << BFS(adj, termeles, dp, megoldas) << endl;
    cout << megoldas.size() << endl;
    for(int i = 0; i < megoldas.size(); i++){
        cout << megoldas[i] << " ";
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms1076 KiB
2Elfogadva0/02ms1084 KiB
3Elfogadva4/41ms1076 KiB
4Elfogadva4/42ms1268 KiB
5Elfogadva4/42ms1076 KiB
6Elfogadva4/42ms1076 KiB
7Elfogadva4/441ms3920 KiB
8Elfogadva6/652ms4396 KiB
9Elfogadva6/663ms4904 KiB
10Elfogadva6/672ms5348 KiB
11Elfogadva6/693ms5808 KiB
12Elfogadva6/6103ms6492 KiB