246982026-02-14 08:29:55CzDaniLogisztikai központcpp14Elfogadva 50/50163ms15856 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define fi first
#define se second

int n, mini, minind;
vector<vector<pii>> adj;
vector<int> f, s, dp, ansv;

void dfs(int v, int p) {
    for (auto u : adj[v]) {
        if (u.fi == p)continue;
        dfs(u.fi, v);
        int c = u.se;
        if (f[u.fi]+c>f[v]) {
            s[v]=f[v];
            f[v]=f[u.fi]+c;
        } else if (f[u.fi]+c>s[v]) {
            s[v]=f[u.fi]+c;
        }
    }
}

void dfs2(int v, int p, int c) {
    if (f[p]==f[v]+c)dp[v]=max(dp[p]+c, s[p]+c);
    else dp[v]=max(f[p]+c, dp[p]+c);
    if (max(dp[v], f[v])<mini) {
        mini=max(dp[v],f[v]);
        ansv.clear();
    }
    if (max(dp[v], f[v])==mini)ansv.push_back(v);
    for (auto u : adj[v]) {
        if (u.fi==p)continue;
        dfs2(u.fi, v, u.se);
    }
}

signed main() {
    cin >> n;
    adj.resize(n+1);
    f.resize(n+1);
    s.resize(n+1, -10000000000000000LL);
    dp.resize(n+1);
    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});
    }
    dfs(1, 0);
    mini=10000000000000000LL;
    f[0]=f[1];
    dfs2(1, 0, 0);
    cout<<mini<<endl;
    sort(ansv.begin(), ansv.end());
    cout << ansv.size() << endl;
    for (int x : ansv)cout<<x<<' ';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/02ms316 KiB
2Elfogadva0/0130ms9012 KiB
3Elfogadva4/41ms316 KiB
4Elfogadva4/42ms316 KiB
5Elfogadva4/41ms316 KiB
6Elfogadva4/41ms316 KiB
7Elfogadva4/41ms508 KiB
8Elfogadva5/52ms316 KiB
9Elfogadva2/2156ms10024 KiB
10Elfogadva2/2142ms10196 KiB
11Elfogadva2/21ms316 KiB
12Elfogadva2/22ms564 KiB
13Elfogadva2/27ms820 KiB
14Elfogadva2/213ms1332 KiB
15Elfogadva2/2144ms9320 KiB
16Elfogadva2/2122ms8760 KiB
17Elfogadva2/2136ms9516 KiB
18Elfogadva2/2112ms7220 KiB
19Elfogadva2/2136ms9644 KiB
20Elfogadva3/3163ms15856 KiB