11142022-03-03 23:23:16peti1234Logisztikai központcpp14Accepted 50/50224ms75100 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;
    max_tav[a].push_back({0, a});
    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});
            sort(max_tav[a].rbegin(), max_tav[a].rend());
            if (max_tav[a].size()>2) {
                max_tav[a].pop_back();
            }
        }
    }
}
void dfs2(int a) {
    volt2[a]=true;
    tav[a]=max_tav[a][0].first;
    tavid[a]=max_tav[a][0].second;
    for (auto p:el[a]) {
        int x=p.first;
        long long y=p.second;
        if (!volt2[x]) {
            if (tavid[a]!=max_tav[x][0].second) {
                max_tav[x].push_back({max_tav[a][0].first+y, max_tav[a][0].second});
            } else if (max_tav[a].size()>1) {
                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});
    }
    dfs(1);
    dfs2(1);
    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/07ms11196 KiB
2Accepted0/0180ms37200 KiB
3Accepted4/46ms12912 KiB
4Accepted4/46ms12932 KiB
5Accepted4/47ms12940 KiB
6Accepted4/49ms12936 KiB
7Accepted4/46ms12988 KiB
8Accepted5/59ms13188 KiB
9Accepted2/2186ms41608 KiB
10Accepted2/2180ms42112 KiB
11Accepted2/29ms15152 KiB
12Accepted2/27ms15448 KiB
13Accepted2/210ms16504 KiB
14Accepted2/214ms18076 KiB
15Accepted2/2162ms41728 KiB
16Accepted2/2157ms41864 KiB
17Accepted2/2171ms45636 KiB
18Accepted2/2118ms40652 KiB
19Accepted2/2131ms45888 KiB
20Accepted3/3224ms75100 KiB