246972026-02-14 08:26:18CzDaniLogisztikai központcpp14Részben helyes 38/50167ms15924 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;
    cout << ansv.size() << endl;
    for (int x : ansv)cout<<x<<' ';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base38/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/0155ms9188 KiB
3Elfogadva4/41ms316 KiB
4Részben helyes2/41ms316 KiB
5Elfogadva4/41ms316 KiB
6Részben helyes2/41ms316 KiB
7Részben helyes2/41ms316 KiB
8Elfogadva5/52ms508 KiB
9Elfogadva2/2141ms10044 KiB
10Elfogadva2/2166ms10224 KiB
11Részben helyes1/21ms316 KiB
12Részben helyes1/22ms564 KiB
13Elfogadva2/26ms820 KiB
14Elfogadva2/212ms1308 KiB
15Elfogadva2/2134ms9232 KiB
16Részben helyes1/2122ms8724 KiB
17Elfogadva2/2141ms9456 KiB
18Részben helyes1/2115ms7172 KiB
19Elfogadva2/2149ms9584 KiB
20Részben helyes1/3167ms15924 KiB