154742025-02-19 19:49:45horkaLogisztikai központcpp17Elfogadva 50/50109ms21812 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int c=1e5+10;
int dp[c],n,ert[c];
bool vis[c];
vector<array<int, 2>> adj[c];
void dfs1(int cs)
{
    vis[cs]=1;
    for(auto &[i,w]:adj[cs])
        if(!vis[i])
    {
        dfs1(i);
        dp[cs]=max(dp[cs],dp[i]+w);
    }
}
int maxi=1e16;
vector<int> ans;
void dfs2(int cs, int font)
{
    vis[cs]=1;
    vector<array<int, 2>> gy;
    int tmp=max(font,dp[cs]);
    ert[cs]=tmp;
    maxi=min(maxi,tmp);
    for(auto &[i,w]:adj[cs])
        if(!vis[i])
    {
        gy.push_back({dp[i]+w,i});
    }
    sort(gy.rbegin(),gy.rend());
    if(gy.empty()) return;
    for(auto &[i,w]:adj[cs])
        if(!vis[i])
    {
        int fent=font+w;
        if(i!=gy[0][1]) fent=max(fent,gy[0][0]+w);
        if(gy.size()>1 && i!=gy[1][1]) fent=max(fent,gy[1][0]+w);
        dfs2(i,fent);
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1; i<n; i++)
    {
        int a,b,c; cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    if(n==1)
    {
        cout<<"0\n1\n1\n";
        return 0;
    }
    if(n==2)
    {
        cout<<adj[1][0][1]<<"\n2\n1 2\n";
        return 0;
    }
    dfs1(1);
    for(int i=1; i<=n;i++)
        vis[i]=0;
    dfs2(1,0);
    for(int i=1; i<=n; i++)
        if(ert[i]==maxi) ans.push_back(i);
    cout<<maxi<<"\n"<<ans.size()<<"\n";
    for(int i:ans)
        cout<<i<<" ";
    cout<<"\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms2852 KiB
2Elfogadva0/0100ms8664 KiB
3Elfogadva4/43ms2612 KiB
4Elfogadva4/43ms2640 KiB
5Elfogadva4/43ms2660 KiB
6Elfogadva4/43ms2616 KiB
7Elfogadva4/43ms2612 KiB
8Elfogadva5/54ms2660 KiB
9Elfogadva2/292ms9496 KiB
10Elfogadva2/294ms9352 KiB
11Elfogadva2/23ms2612 KiB
12Elfogadva2/24ms2868 KiB
13Elfogadva2/27ms3348 KiB
14Elfogadva2/29ms3384 KiB
15Elfogadva2/276ms8852 KiB
16Elfogadva2/275ms8512 KiB
17Elfogadva2/293ms9008 KiB
18Elfogadva2/259ms7472 KiB
19Elfogadva2/283ms10656 KiB
20Elfogadva3/3109ms21812 KiB