155682025-02-20 14:14:13999Logisztikai központcpp17Elfogadva 50/50178ms19768 KiB
// Source: https://usaco.guide/general/io

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

const int INF = 1e12;

vector<int> dpf;
vector<array<pair<int,int>,2>> dpl;

void dfsl(vector<vector<pair<int,int>>>& v, int node, int p){
    pair<int,int> max1,max2;
    max1 = max2 = {0,-1};
    for(auto[i,c]:v[node]){
        if(i==p)continue;
        dfsl(v,i,node);
        pair<int,int> q={dpl[i][0].first+c,i};
        if(max1<q){
            max2=max1;
            max1=q;
        }
        else if(max2<q){
            max2=q;
        }
    }
    dpl[node]={max1,max2};
}

void dfsf(vector<vector<pair<int,int>>>& v, int node, int p){
    for(auto[i,c]:v[node]){
        if(i==p)continue;
        dpf[i]=max(dpf[node],(dpl[node][0].second==i?dpl[node][1].first:dpl[node][0].first))+c;
        dfsf(v,i,node);
    }
}

signed main() {
    int n;cin>>n;
    vector<vector<pair<int,int>>> v(n);
    dpf.resize(n);
    dpl.assign(n,{{{0,-1},{0,-1}}});
    for(int i = 0;i<n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[--a].push_back({--b,c});
        v[b].push_back({a,c});
    }
    dfsl(v,0,-1);
    pair<int,int> max1,max2;
    max1 = max2 = {-1,-1};
    for(auto[i,c]:v[0]){
        pair<int,int> q={c+dpl[i][0].first,i};
        if(max1<q){
            max2=max1;
            max1=q;
        }
        else if(max2<q){
            max2=q;
        }
    }
    dfsf(v,0,-1);
    vector<int> ans;
    int minv=INF;
    for(int i = 0;i<n;i++){
        if(max(dpf[i],dpl[i][0].first)==minv)ans.push_back(i+1);
        else if(max(dpf[i],dpl[i][0].first)<minv){
            minv=max(dpf[i],dpl[i][0].first);
            ans.clear();
            ans.push_back(i+1);
        }
    }
    cout<<minv<<endl<<ans.size()<<endl;
    for(int i : ans)cout<<i<<' ';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms508 KiB
2Elfogadva0/0135ms10548 KiB
3Elfogadva4/41ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/41ms316 KiB
6Elfogadva4/41ms316 KiB
7Elfogadva4/41ms316 KiB
8Elfogadva5/52ms316 KiB
9Elfogadva2/2163ms11748 KiB
10Elfogadva2/2150ms11664 KiB
11Elfogadva2/21ms316 KiB
12Elfogadva2/22ms564 KiB
13Elfogadva2/27ms820 KiB
14Elfogadva2/213ms1328 KiB
15Elfogadva2/2144ms10580 KiB
16Elfogadva2/2136ms10036 KiB
17Elfogadva2/2145ms10960 KiB
18Elfogadva2/2114ms8204 KiB
19Elfogadva2/2143ms11156 KiB
20Elfogadva3/3178ms19768 KiB