258752026-03-05 20:25:42csdavidLogisztikai központcpp17Elfogadva 50/50194ms16692 KiB
#include <iostream>
#include <vector>

using namespace std;

long long n;
vector<pair<long long, long long>> adj[100001];
long long distan[2][100001];
long long current = 0;
long long previous[100001];
long long wprev[100001];
long long furthest1, furthest2;
long long maxdist = 0;

void dfs(long long x, long long p, long long dist){
    distan[current][x] = dist;
    if (dist > maxdist){
        maxdist = dist;
        furthest1 = x;
    }
    previous[x] = p;
    for (auto [next, w] : adj[x]){
        if (next != p){
            wprev[next] = w;
            dfs(next, x, dist + w);
        }
    }
}

int main(){
    //freopen("in.txt", "r", stdin);
    cin >> n;
    for (long long i = 0; i < n - 1; i++){
        long long a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    dfs(1, -1, 0);
    furthest2 = furthest1;
    dfs(furthest1, -1, 0);
    current = 1;
    dfs(furthest1, -1, 0);
    long long d = maxdist;
    long long x = furthest1;
    wprev[furthest2] = 0;
    /*while (true){
        if (x == furthest2){
            cout << maxdist << '\n' << 1 << '\n' << x << '\n';
            return 0;
        }
        if (maxdist % 2 == 0 && d == maxdist / 2){
            cout << maxdist / 2 << '\n' << 1 << '\n' << x << '\n';
            return 0;
        }
        if (d - wprev[x] < maxdist / 2.0){
            long long sol1 = x, sol2 = previous[x];
            long long val1 = max(d, maxdist - d);
            long long val2 = max(d + wprev[x], maxdist - d - wprev[x]);
            if (val1 == val2){
                cout << val1 << '\n' << 2 << '\n' << min(sol1, sol2) << '\n' << max(sol1, sol2) << '\n';
            }
            else{
                cout << min(val1, val2) << '\n' << 1 << '\n';
                if (val1 < val2){
                    cout << sol1 << '\n';
                }
                else{
                    cout << sol2 << '\n';
                }
            }
            return 0;
        }

        d -= wprev[x];
        x = previous[x];
    }*/
    long long ans = 1e18;
    for (int i = 1; i <= n; i++){
        ans = min(ans, max(distan[0][i], distan[1][i]));
    }
    vector<int> answers;
    for (int i = 1; i <= n; i++){
        if (max(distan[0][i], distan[1][i]) == ans){
            answers.push_back(i);
        }
    }
    cout << ans << '\n' << answers.size() << '\n';
    for (int x : answers){
        cout << x << '\n';
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms2612 KiB
2Elfogadva0/0138ms10036 KiB
3Elfogadva4/43ms2612 KiB
4Elfogadva4/44ms2612 KiB
5Elfogadva4/43ms2612 KiB
6Elfogadva4/43ms2712 KiB
7Elfogadva4/43ms2636 KiB
8Elfogadva5/54ms2612 KiB
9Elfogadva2/2194ms10964 KiB
10Elfogadva2/2194ms10976 KiB
11Elfogadva2/23ms2612 KiB
12Elfogadva2/24ms2868 KiB
13Elfogadva2/28ms2980 KiB
14Elfogadva2/214ms3472 KiB
15Elfogadva2/2143ms10136 KiB
16Elfogadva2/2128ms9684 KiB
17Elfogadva2/2172ms10292 KiB
18Elfogadva2/2119ms8500 KiB
19Elfogadva2/2143ms10444 KiB
20Elfogadva3/3167ms16692 KiB