11152022-03-03 23:30:20peti1234Logisztikai központcpp14Accepted 50/50252ms76076 KiB
#include <bits/stdc++.h>

using namespace std;
const int c=100005;
int n;
long long tav[c], tavid[c];
vector<pair<int, long long> > el[c];
vector<pair<long long, int> > max_tav[c];
bool volt[c], volt2[c];
void dfs(int a) {
    volt[a]=true;

    // a max_tav az a-bol elerheto legnagyobb tavolsagokat tarolja (tavolsak, csucs) formaban, forditva rendezve (ez igy nem tul elegans)
    max_tav[a].push_back({0, a});
    // onmagatol 0 tavol van

    for (auto p:el[a]) {
        int x=p.first;
        long long y=p.second;
        if (!volt[x]) {
            dfs(x);
            max_tav[a].push_back({max_tav[x][0].first+y, max_tav[x][0].second});
            // a gyerekeitol tavoli csucsokat kell figyelni

            sort(max_tav[a].rbegin(), max_tav[a].rend());
            if (max_tav[a].size()>2) {
                max_tav[a].pop_back();
            }
            // eleg a ket legjobbat megjegyzni, talan felesleges (szinten nem tul szep)
        }
    }
}
void dfs2(int a) {
    // egy hasonlo melysegi bejaras
    volt2[a]=true;
    tav[a]=max_tav[a][0].first;
    // tav[a] a lenyeg

    tavid[a]=max_tav[a][0].second;
    for (auto p:el[a]) {
        int x=p.first;
        long long y=p.second;
        if (!volt2[x]) {
            // a kovetkezo csucshoz kell megtalalni a legtavolabbi csucsot (ami a-n keresztul megy)
            if (tavid[a]!=max_tav[x][0].second) {
                // ha nem az (a-x) elen ment at ketszer, akkor a legnagyobb
                max_tav[x].push_back({max_tav[a][0].first+y, max_tav[a][0].second});
            } else if (max_tav[a].size()>1) {
                // egyebkent a masodik legnagyobbat kell tovabb vinni
                max_tav[x].push_back({max_tav[a][1].first+y, max_tav[a][1].second});
            }
            sort(max_tav[x].rbegin(), max_tav[x].rend());
            dfs2(x);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i=1; i<n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        el[a].push_back({b, c});
        el[b].push_back({a, c});
    }
    // szomszedok listaja (csucs, tavolsag) parban

    dfs(1);
    // legyen a fanak 1 a gyokere, es hatarozzuk meg minden csucsban a ket alatta levo legtavolabbi csucsot

    dfs2(1);
    // ezekkel az informaciokkal mar ki lehet talalni, minden csucsra, hogy milyen messze van a tole legmesszebb levo csucs


    // a tav tombben van az osszes fontos informacio
    long long ert=tav[1], cnt=0;
    for (int i=1; i<=n; i++) {
        if (tav[i]<ert) {
            ert=tav[i];
            cnt=0;
        }
        if (ert==tav[i]) {
            cnt++;
        }
    }
    cout << ert << "\n";
    cout << cnt << "\n";
    for (int i=1; i<=n; i++) {
        if (tav[i]==ert) {
            cout << i << " ";
        }
    }
    cout << "\n";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/07ms11280 KiB
2Accepted0/0144ms37136 KiB
3Accepted4/46ms12924 KiB
4Accepted4/46ms12928 KiB
5Accepted4/48ms12928 KiB
6Accepted4/46ms12936 KiB
7Accepted4/46ms12960 KiB
8Accepted5/58ms13232 KiB
9Accepted2/2168ms41612 KiB
10Accepted2/2159ms43204 KiB
11Accepted2/26ms16244 KiB
12Accepted2/28ms16660 KiB
13Accepted2/29ms17680 KiB
14Accepted2/214ms19180 KiB
15Accepted2/2149ms42808 KiB
16Accepted2/2142ms42904 KiB
17Accepted2/2157ms46616 KiB
18Accepted2/2127ms41632 KiB
19Accepted2/2130ms46964 KiB
20Accepted3/3252ms76076 KiB