Cod sursa(job #2837957)

Utilizator QwertyDvorakQwerty Dvorak QwertyDvorak Data 22 ianuarie 2022 22:13:06
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
using ll = long long;
const string fn = "darb";

ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

int n, ans = 0;
int dp[100005];
vector<int> g[100005];

void dfs(int x, int dad){
    int best1, best2;
    best1 = best2 = 0;
    for(int son : g[x]){
        if(son != dad){
            dfs(son, x);
            if(dp[son] > best1)
                best2 = best1, best1 = dp[son];
            else if(dp[son] > best2)
                best2 = dp[son];
        }
    }
    dp[x] = best1 + 1;
    ans = max(ans, best1 + best2 + 1);
}

int main(){
  
    int x, y;
    fin >> n;
    
    for(int i = 1; i < n; ++i){
        fin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1, 0);

    fout << ans << '\n';
    fin.close();
    fout.close();
    return 0;
}