Tree Practice 1

    1#include <bits/stdc++.h>
    2using namespace std;
    3const long long INF = 4e18;
    4int n;
    5vector<vector<pair<int, int>>> adj;
    6vector<long long> dijkstra(int start) {
    7    vector<long long> dist(n + 1, INF);
    8    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    9    dist[start] = 0;
    10    pq.push({0, start});
    11    while (!pq.empty()){
    12        auto cur = pq.top();
    13        pq.pop();
    14        long long d = cur.first;
    15        int u = cur.second;
    16        if (d != dist[u]) continue;
    17        for (auto edge : adj[u]){
    18            int v = edge.first;
    19            int w = edge.second;
    20            long long nd = d + w;
    21            if (nd < dist[v]) {
    22                dist[v] = nd;
    23                pq.push({nd, v});
    24            }
    25        }
    26    }
    27    return dist;
    28}
    29int main(){
    30    ios::sync_with_stdio(0);
    31    cin.tie(0);
    32    cin >> n;
    33    adj.assign(n + 1, {});
    34    for (int i = 0; i < n - 1; i++){
    35        int u, v, w;
    36        cin >> u >> v >> w;
    37        adj[u].push_back({v, w});
    38        adj[v].push_back({u, w});
    39    }
    40    vector<long long> dist1 = dijkstra(1);
    41    int A = 1;
    42    for (int i = 1; i <= n; i++){
    43        if (dist1[i] > dist1[A]) A = i;
    44    }
    45    vector<long long> distA = dijkstra(A);
    46    int B = A;
    47    for (int i = 1; i <= n; i++){
    48        if (distA[i] > distA[B]) B = i;
    49    }
    50    long long diameter = distA[B];
    51    vector<long long> distB = dijkstra(B);
    52    long long radius = INF;
    53    for (int i = 1; i <= n; i++) {
    54        long long ecc = max(distA[i], distB[i]);
    55        if (ecc < radius) radius = ecc;
    56    }
    57    cout << diameter << "\n" << radius << "\n";
    58    return 0;
    59}
    60