154732025-02-19 19:48:03horkaLogisztikai központcpp17Partially correct 38/50127ms23272 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int c=1e5+10;
int dp[c],n;
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=1e15;
vector<int> ans;
void dfs2(int cs, int font)
{
    //cout<<cs<<" "<<font<<endl;
    vis[cs]=1;
    vector<array<int, 2>> gy;
    int tmp=max(font,dp[cs]);
    if(tmp<maxi)
    {
        ans.clear();
        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);
    }
    if(maxi==tmp) ans.push_back(cs);
}
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);
    cout<<maxi<<"\n"<<ans.size()<<"\n";
    for(int i:ans)
        cout<<i<<" ";
    cout<<"\n";
}
SubtaskSumTestVerdictTimeMemory
base38/50
1Accepted0/03ms2612 KiB
2Accepted0/087ms7984 KiB
3Accepted4/43ms2612 KiB
4Partially correct2/43ms2804 KiB
5Accepted4/43ms2612 KiB
6Partially correct2/43ms2612 KiB
7Partially correct2/43ms2612 KiB
8Accepted5/53ms2976 KiB
9Accepted2/286ms8740 KiB
10Accepted2/2105ms8792 KiB
11Partially correct1/23ms2612 KiB
12Partially correct1/23ms2868 KiB
13Accepted2/24ms3072 KiB
14Accepted2/28ms3392 KiB
15Accepted2/275ms8160 KiB
16Partially correct1/283ms7972 KiB
17Accepted2/275ms8244 KiB
18Partially correct1/265ms6848 KiB
19Accepted2/271ms10652 KiB
20Partially correct1/3127ms23272 KiB