10302022-02-25 17:20:18Kevinke12Tevefarmcpp14Elfogadva 50/50112ms20948 KiB
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int N;
ll be1;
vector<int> ellista[100005];
vector<ll> tevek;
pair<ll, ll> ans[100005]; //benne, nincs benne

pair<ll, ll> Mely(int cs)
{
    pair<ll, ll> akt; akt.first=0; akt.second=0;
    akt.first=tevek[cs-1];

    for(int a:ellista[cs])
    {

        //cout << cs << ":" << a << "\n";
        pair<ll, ll> uj;
        uj = Mely(a);
        //akt.first+=uj.second;
        akt.second += max(uj.first, uj.second);
    }
    ans[cs]=akt;
    return akt;
}
vector<int> ki;

void Mely2(int cs)
{
    if(ans[cs].first>ans[cs].second)
        ki.push_back(cs);
    else
    {
        for(int a:ellista[cs])
        {
            Mely2(a);
        }
    }
}


int main()
{
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        cin >> be1;
        tevek.push_back(be1);
    }
    for(int i = 2; i <= N; i++)
    {
        cin >> be1;
        ellista[be1].push_back(i);
    }
    Mely(1);

    /*for(int i = 1; i <= N; i++)
    {
        cout << i << ":" << ans[i].first << " " << ans[i].second << "\n";
    }*/

    cout << max(ans[1].first, ans[1].second) << "\n";
    Mely2(1);
    cout << ki.size() << "\n";
    for(int a:ki)
        cout << a << " "; cout << "\n";

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/04ms6544 KiB
2Elfogadva0/04ms6660 KiB
3Elfogadva4/43ms6620 KiB
4Elfogadva4/43ms6628 KiB
5Elfogadva4/43ms6648 KiB
6Elfogadva4/44ms6700 KiB
7Elfogadva4/443ms11344 KiB
8Elfogadva6/652ms12912 KiB
9Elfogadva6/665ms14668 KiB
10Elfogadva6/674ms16444 KiB
11Elfogadva6/698ms18472 KiB
12Elfogadva6/6112ms20948 KiB