Cod sursa(job #3268327)

Utilizator AlexPlesescuAlexPlesescu AlexPlesescu Data 14 ianuarie 2025 15:13:39
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;
#define int long long int
#define pb push_back
#define sz(x) (int)(x.size())
#define all(a) a.begin(), a.end()
#define nl '\n'
const int N = 3e5 + 5, INF = 1e9, mod = 998244353;

int n, best_node, mx_1, darb, dist[N];
vector<int> g[N];

void bfs(int start, int cnt) {
    queue<int> Q;
    Q.push(start);
    fill(dist + 1, dist + n + 1, INF);
    dist[start] = 1;
    int mx = 0;
    while (!Q.empty()) {
        int node = Q.front();
        if (dist[node] > mx) {
            mx = dist[node];
            if (cnt == 1)
                best_node = node;
        }
        Q.pop();
        for (auto it : g[node]) {
            if (dist[node] + 1 < dist[it]) {
                dist[it] = dist[node] + 1;
                Q.push(it);
            }
        }
    }
    if (cnt == 1 && mx > mx_1) {
        mx_1 = mx;
    }
    else if (cnt == 2 && mx > darb) {
        darb = mx;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("darb.in", "r", stdin);
    freopen("darb.out", "w", stdout);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    bfs(1, 1);
    bfs(best_node, 2);
    cout << darb;
}