20432022-12-15 21:08:16TomaSajtLogisztikai központcpp17Partially correct 38/50103ms31644 KiB
#include <bits/stdc++.h>
#define speed ios::sync_with_stdio(0);cin.tie(0)
using namespace std;
typedef long long ll;

vector<vector<pair<int, ll>>> g;
vector<ll> dist;
vector<int> par;

void dfs(int u) {
    for (auto [v, w] : g[u]) {
        if (dist[v] != -1) continue;
        dist[v] = dist[u] + w;
        par[v] = u;
        dfs(v);
    }
}

int main() {
    speed;
    int n;
    cin >> n;
    g.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        g[u].push_back({ v,w });
        g[v].push_back({ u,w });
    }
    par.assign(n + 1, -1);
    dist.assign(n + 1, -1);
    dist[1] = 0;
    dfs(1);
    int s = max_element(dist.begin() + 1, dist.end()) - dist.begin();
    par.assign(n + 1, -1);
    dist.assign(n + 1, -1);
    dist[s] = 0;
    dfs(s);
    int e = max_element(dist.begin() + 1, dist.end()) - dist.begin();
    ll diam = dist[e];
    int curr = e;
    map<ll, vector<int>> distLists;
    while (curr != -1) {
        ll currDistS = dist[curr];
        ll currDistE = diam - currDistS;
        distLists[max(currDistS, currDistE)].push_back(curr);
        curr = par[curr];
    }
    auto& [d, l] = *distLists.begin();
    sort(l.begin(), l.end());
    cout << d << '\n' << l.size() << '\n';
    for (auto a : l) cout << a << ' ';
}
SubtaskSumTestVerdictTimeMemory
base38/50
1Accepted0/03ms1732 KiB
2Accepted0/064ms17360 KiB
3Accepted4/42ms2064 KiB
4Partially correct2/42ms2268 KiB
5Accepted4/42ms2484 KiB
6Partially correct2/42ms2684 KiB
7Partially correct2/42ms2912 KiB
8Accepted5/53ms3348 KiB
9Accepted2/268ms20444 KiB
10Accepted2/271ms20572 KiB
11Partially correct1/23ms3676 KiB
12Partially correct1/23ms4068 KiB
13Accepted2/24ms4724 KiB
14Accepted2/28ms5752 KiB
15Accepted2/265ms19624 KiB
16Partially correct1/261ms19128 KiB
17Accepted2/267ms20052 KiB
18Partially correct1/250ms15980 KiB
19Accepted2/259ms20452 KiB
20Partially correct1/3103ms31644 KiB