246492026-02-13 09:15:13Pedri26Logisztikai központcpp11Accepted 50/5050ms6396 KiB
// Source: https://usaco.guide/general/io

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

int n, kovel[200001], mutat[200001], elsoel[200001], elsuly[200001], eldb;
long long tav[100001], distA[100001], distB[100001];

void elhozzaadas(int a, int b, int w)
{
    eldb++;
    kovel[eldb]=elsoel[a];
    elsoel[a]=eldb;
    mutat[eldb]=b;
    elsuly[eldb]=w;
}

void szbejar(int i, long long* tavol)
{
    for(int j=1;j<=n;j++)tavol[j]=-1;
    int vsor[100001], elso=0, utolso=0;
    vsor[elso]=i;
    tavol[i]=0;
    while(elso<=utolso)
    {
        for(int k=elsoel[vsor[elso]];k!=0;k=kovel[k])
        {
            if(tavol[mutat[k]]==-1)
            {
                tavol[mutat[k]]=tavol[vsor[elso]]+elsuly[k];
                utolso++;
                vsor[utolso]=mutat[k];
            }
        }
        elso++;
    }

}

int main() {
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int a, b, w;
        cin>>a>>b>>w;
        elhozzaadas(a, b, w);
        elhozzaadas(b, a, w);
    }
    szbejar(1, tav);
    int A=1;
    for(int i=1;i<=n;i++)
    {
        if(tav[i]>tav[A])A=i;
    }
    szbejar(A, distA);
    int B=A;
    for(int i=1;i<=n;i++)
    {
        if(distA[i]>distA[B])B=i;
    }
    szbejar(B, distB);
    long long t=1e18;
    for(int i=1;i<=n;i++)
    {
        long long maxtav=max(distA[i], distB[i]);
        if(maxtav<t)t=maxtav;
    }
    long long kozpont[100001], s=0;
    for(int i=1;i<=n;i++)
    {
        if(max(distA[i], distB[i])==t)
        {
            s++;
            kozpont[s]=i;
        }
    }
    cout<<t<<endl;
    cout<<s<<endl;
    for(int i=1;i<=s;i++)
    {
        cout<<kozpont[i]<<" ";
    }

    
    


    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms316 KiB
2Accepted0/045ms5172 KiB
3Accepted4/41ms316 KiB
4Accepted4/41ms316 KiB
5Accepted4/41ms316 KiB
6Accepted4/41ms316 KiB
7Accepted4/41ms316 KiB
8Accepted5/51ms316 KiB
9Accepted2/250ms5812 KiB
10Accepted2/248ms6396 KiB
11Accepted2/21ms316 KiB
12Accepted2/22ms564 KiB
13Accepted2/23ms748 KiB
14Accepted2/24ms820 KiB
15Accepted2/246ms5496 KiB
16Accepted2/245ms5060 KiB
17Accepted2/248ms5656 KiB
18Accepted2/235ms4504 KiB
19Accepted2/243ms5928 KiB
20Accepted3/350ms5840 KiB