Zadanie algorytmiczne z drzewem

Cześć,
Rozwiązuję to zadanie:
https://szkopul.edu.pl/problemset/problem/pXcijJbDyC_jRAjkoxBH9sCO/site/?key=statement
Jestem na etapie pierwszym, czyli próbuję odnaleźć liczbę W oznaczająca maksymalną sumę współczynników atrakcyjności (pierwszy wiersz wyjścia). Za wypisanie jej prawidłowo dostaje się 40% pkt. za test. Niestety od dłuższego czasu zatrzymałem się w momencie, w którym dostaje 40% za wszystkie testy oprócz jednego - 4d, w którym zamiast 473348 mój program wypisuje 473347. Zrobiłem "rekonesans" (wysyłając mnóstwo zgłoszeń i zamiast odpowiedzi wypisując wejście) i wiem, że w tym teście wszystkie współczynniki wynoszą 1, a n = 999999. Niestety nic mi to nie dało i wciąż nie mogę odnaleźć błędu.
Oto co robi mój program:

1. Po wczytaniu danych szukam wierzchołka odpowiedniego na korzeń (czyli jakiegokolwiek, który nie jest liściem) i buduję drzewo (funkcja budujDrzewo).
2. Wywołuję funkcję rekurencyjną oblicz, która oblicza wartości dla danego wierzchołka na podstawie wyników jego dzieci:

• wynikO - wynik dla danego wierzchołka, jeśli jest wierzchołkiem odpoczynkowym: suma jego wszystkich dzieci + najbardziej korzystna droga w dół
• wynikZ - wynik dla wierzchołka, jeśli jest zwiedzany: punkty za wierzchołek + najbardziej korzystna droga w dół
• Wyniki ścieżek dla wierzchołka jeśli byłby najwyższym wierzchołkiem w ścieżce (startowym).

Tutaj kod:

#include <bits/stdc++.h>
using namespace std;

struct Wezel
{
    int numer;
    Wezel* ojciec;
    vector<Wezel*> dzieci;
    long long punkty;
    long long wynikO,wynikZ;
    int glebokosc;
    bool obliczone;
};

const int MAX_N=1000000;
int punkty[MAX_N];
vector<int> polaczenia[MAX_N];
int glebokosci[MAX_N];

long long wynikMaksymalny=0;
Wezel* wezelStartowy;

void budujDrzewo(Wezel* korzen)
{
    stack<pair<Wezel*,int>> s;
    s.push(make_pair(korzen,0));
    while(!s.empty())
    {
        pair<Wezel*,int> p = s.top();
        s.pop();
        for(int i = 0; i < polaczenia[p.second].size(); ++i)
        {
            if(glebokosci[polaczenia[p.second][i]]!=-1)
            {
                continue;
            }
            Wezel* dziecko = new Wezel();
            dziecko->numer=polaczenia[p.second][i];
            dziecko->ojciec=p.first;
            dziecko->punkty=punkty[polaczenia[p.second][i]];
            dziecko->glebokosc=p.first->glebokosc+1;
            glebokosci[dziecko->numer]=dziecko->glebokosc;
            p.first->dzieci.push_back(dziecko);
            dziecko->wynikZ=0;
            dziecko->wynikO=0;
            dziecko->obliczone=0;
            s.push(make_pair(dziecko,polaczenia[p.second][i]));
        }
    }    
}

void oblicz(Wezel* w)
{
    w->obliczone=1;
    
    long long sumaDzieci=0;
    pair<long long, long long> najwiekszeZ[2] { make_pair(0,0), make_pair(0,0)};
    long long najwiekszeO[2] {0,0};
    
    for(int i = 0; i < w->dzieci.size(); ++i)
    {
        if(!w->dzieci[i]->obliczone)
            oblicz(w->dzieci[i]);
            
        sumaDzieci += w->dzieci[i]->punkty;
        
        if(w->dzieci[i]->wynikZ > najwiekszeZ[0].first || (w->dzieci[i]->wynikZ == najwiekszeZ[0].first && w->dzieci[i]->punkty <= najwiekszeZ[0].second))
        {
            najwiekszeZ[1] = najwiekszeZ[0];
            najwiekszeZ[0].first = w->dzieci[i]->wynikZ;
            najwiekszeZ[0].second = w->dzieci[i]->punkty;
        }
        else if(w->dzieci[i]->wynikZ > najwiekszeZ[1].first || (w->dzieci[i]->wynikZ == najwiekszeZ[1].first && w->dzieci[i]->punkty <= najwiekszeZ[1].second))
        {
            najwiekszeZ[1].first = w->dzieci[i]->wynikZ;
            najwiekszeZ[1].second = w->dzieci[i]->punkty;
        }
        
        if(w->dzieci[i]->wynikO > najwiekszeO[0])
        {
            najwiekszeO[1] = najwiekszeO[0];
            najwiekszeO[0] = w->dzieci[i]->wynikO;
        }
        else if(w->dzieci[i]->wynikO > najwiekszeO[1])
        {
            najwiekszeO[1] = w->dzieci[i]->wynikO;
        }
    }
    
    sumaDzieci -= najwiekszeZ[0].second;
    w->wynikO = sumaDzieci + najwiekszeZ[0].first;
    w->wynikZ = w->punkty + najwiekszeO[0];
    
    long long wynikSciezkiZ = w->wynikZ + najwiekszeO[1];
    long long wynikSciezkiO = w->wynikO + najwiekszeZ[1].first - najwiekszeZ[1].second;
    long long wynikWezla = max(wynikSciezkiZ, wynikSciezkiO);
    
    //cout << "Wynik wezla " << w->numer+1 << ": " << wynikWezla << endl;
    
    if(wynikWezla > wynikMaksymalny)
    {
        wynikMaksymalny = wynikWezla;
        wezelStartowy = w;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin>>n;
    
    for(int i = 0; i < n; ++i)
    {
        cin>>punkty[i];
        glebokosci[i]=-1;
    }
    for(int i = 0; i < n-1; ++i)
    {
        int a,b;
        cin>>a>>b;
        --a;
        --b;
        polaczenia[a].push_back(b);
        polaczenia[b].push_back(a);
    }
    
    int k=0;
    for(int i = 0; i < MAX_N; ++i)
    {
        if(polaczenia[i].size()>0)
        {
            k=i;
            break;
        }
    }
    
    Wezel* korzen = new Wezel();
    korzen->punkty=punkty[k];
    korzen->numer=k;
    korzen->glebokosc=0;
    glebokosci[korzen->numer]=0;
    budujDrzewo(korzen);
    
    oblicz(korzen);
    cout << wynikMaksymalny << "\n1\n1";
}

Skończyły mi się już pomysły na to, co może iść nie tak. Napisałem nawet algorytm od nowa i niestety wynik jest ten sam. Proszę o pomoc.

Moje spostrzeżenia:

• nie używaj zmiennych globalnych
• tablica wektorów (?) vector<int> polaczenia[MAX_N] - używaj albo zwykłych tablic [][] albo wektorów vector<vector<int>> - nie mieszaj tych rzeczy
• jak tworzysz obiekty za pomocą new to pamiętaj o ich usunięciu delete.
• używaj dynamicznych kontenerów vector do przechowywania i przetwarzania danych.

Zobacz jak można przebudować ten kod używając prostej obiektowości.

#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <set>

using namespace std;

struct City
{
    int id {0};
    int attractivness {0};
    bool visited {false};
};

using cCityIter = vector<City>::const_iterator;

struct FindResult
{
    int totalCitiesAttractiveness {0};
    int numberOfVisitedCities {0};
    vector<int> itineraryPath;
};

class ItineraryFinder
{
public:

    void addCityAttractions( const vector<int>& city_attraction )
    {
        for( size_t index=0 ; index<city_attraction.size() ; ++index )
        {
            cities.push_back( {index,city_attraction[index],false} );
        }
    }

    void addRoad( int from , int to )
    {
        if( from<0 || from>=cities.size() || to<0 || to>=cities.size() ) return;
        road[from].insert( cities.begin() + to );
        road[to].insert( cities.begin() + from );
    }

    FindResult findOptimalItinerary()
    {
        FindResult result;
        //
        //
        // twoja implementacja
        //
        //
        auto cityPath = {0,1,2,3,4}; // wynik z góry wstawiony dla tego konkretnego przypadku
        return { calculateTotalAttraction(cityPath), calculateNumberOfVistedCities(cityPath.size()) , cityPath };
    }

private:

    map<int,set<cCityIter>> road;
    vector<City> cities;

    int calculateTotalAttraction( const vector<int>& itinerary ) const
    {
        int totalAttraction {0};
        for( size_t city=0 ; city<itinerary.size() ; city+=2 ) // obliczamy atrakcyjnoœc co drugiego miasta
        {
            totalAttraction += cities.at(city).attractivness ;
        }
        return totalAttraction;
    }

    int calculateNumberOfVistedCities( int pathLength ) const
    {
        return pathLength%2==0 ? pathLength/2 : (pathLength+1)/2;
    }
};

int main()
{
    ItineraryFinder itineraryFinder;

    itineraryFinder.addCityAttractions( { 12,1,5,1,17} ); // miasto numer 0 posiada atrakcyjnoœæ 12 , miasto numer 1 ma atrakcyjnoœc 1 itd.
    itineraryFinder.addRoad( 0,1 );
    itineraryFinder.addRoad( 1,2 );
    itineraryFinder.addRoad( 2,3 );
    itineraryFinder.addRoad( 3,4 );

    auto result = itineraryFinder.findOptimalItinerary();

    cout << "Total city attraction = " << result.totalCitiesAttractiveness << "\n";
    cout << "Number of city visited = " << result.numberOfVisitedCities << "\n";
    for( const auto& city : result.itineraryPath )
    {
        cout << city << " ";
    }

    return 0;
}

IMHO na pewno będzie łatwiej napisać poprawnie działający algorytm używając powyższego schematu.

Dziękuję za wskazówki, niestety mój problem jest wciąż aktualny. Tak na marginesie, co jest złego w mieszaniu wektorów z tablicami?

Wszystko zależy od kontekstu, inaczej się pisze kod na konkursy algorytmiczne, a inaczej kod produkcyjny. Te uwagi powyżej dotyczyły kodu produkcyjnego, a nie konkursowego. Użycie zmiennych globalnych, nie zwalnianie pamięci, mieszanie kontenerów, czy użycie tablic to powszechne praktyki w kodzie konkursowym, tu wszystko jest dozwolone byle tylko dostać maks punktów za zadanie. Nikt się nie przejmuje obiektowością czy modyfikatorami dostępu skoro kod trzeba napisać szybko, zaliczyć i wyrzucić po kilku godzinach od napisania.