95872024-02-23 13:17:20AblablablaLogisztikai központcpp17Elfogadva 50/50150ms34824 KiB
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll, ll> pii;

vector<vector<pii>> csucsok;
vector<ll> elso;
vector<ll> masodik;
vector<ll> maxInd;

ll dfs(ll akt, ll elozo){
    for(ll i = 0; i < csucsok[akt].size(); i++){
        pii x = csucsok[akt][i];

        if(x.first == elozo) continue;

        ll tav = dfs(x.first, akt) + x.second;

        if(tav >= elso[akt]){
            masodik[akt] = elso[akt];
            elso[akt] = tav;
            maxInd[akt] = i;
        } else if(tav > masodik[akt]){
            masodik[akt] = tav;
        }
    }

    return elso[akt];
}

void dfs2(ll akt, ll elozo, ll folotte){
    if(folotte >= elso[akt]){
        masodik[akt] = elso[akt];
        elso[akt] = folotte;
        maxInd[akt] = -1;
    } else if(folotte > masodik[akt]){
        masodik[akt] = folotte;
    }

    for(ll i = 0; i < csucsok[akt].size(); i++){
        pii x = csucsok[akt][i];

        if(x.first == elozo) continue;

        dfs2(x.first, akt, (maxInd[akt] == i ? masodik[akt] : elso[akt]) + x.second);
    }
}

int main(){
    ll n;
    cin >> n;

    csucsok.assign(n, vector<pii>());
    for(ll i = 0; i < n - 1; i++){
        ll a, b, c;
        cin >> a >> b >> c;
        a--; b--;

        csucsok[a].push_back({b, c});
        csucsok[b].push_back({a, c});
    }

    elso.assign(n, 0);
    masodik.assign(n, 0);
    maxInd.assign(n, 0);
    dfs(0, -1);

    dfs2(0, -1, 0);

    ll mini = LONG_MAX;
    vector<ll> indexek;
    for(ll i = 0; i < n; i++){
        if(elso[i] < mini){
            mini = elso[i];
            indexek.clear();
            indexek.push_back(i);
        } else if(elso[i] == mini){
            indexek.push_back(i);
        }
    }

    assert(mini != LONG_MAX);
    cout << mini << "\n";
    cout << indexek.size() << "\n";
    for(ll x : indexek){
        cout << x + 1 << " ";
    }
    cout << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1960 KiB
2Elfogadva0/0128ms19524 KiB
3Elfogadva4/43ms2160 KiB
4Elfogadva4/43ms2328 KiB
5Elfogadva4/42ms2380 KiB
6Elfogadva4/43ms2508 KiB
7Elfogadva4/43ms2628 KiB
8Elfogadva5/54ms2692 KiB
9Elfogadva2/2138ms22000 KiB
10Elfogadva2/2138ms22004 KiB
11Elfogadva2/23ms2896 KiB
12Elfogadva2/24ms3360 KiB
13Elfogadva2/28ms4140 KiB
14Elfogadva2/214ms5220 KiB
15Elfogadva2/2136ms21292 KiB
16Elfogadva2/2125ms20592 KiB
17Elfogadva2/2137ms22128 KiB
18Elfogadva2/2104ms17404 KiB
19Elfogadva2/2144ms22528 KiB
20Elfogadva3/3150ms34824 KiB