Cod sursa(job #2779390)

Utilizator andcovAndrei Covaci andcov Data 3 octombrie 2021 16:14:58
Problema Diametrul unui arbore Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
//
// Created by Andrei Covaci on 03.09.2021.
//

#include <fstream>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

#define INPUT "darb.in"
#define OUTPUT "darb.out"
//#define INPUT "input.in"
//#define OUTPUT "output.out"

int n, maxg;
unordered_map<int, vector<int>> adj;
bool vis[100001];

int read() {
    ifstream in(INPUT);

    int a, b;

    in >> n;
    n--;
    for(; n; --n) {
        in >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }

    in.close();
    return a;
}

int solve(int n) {
    vis[n] = true;

    if(adj[n].size() == 1) {
        if (!vis[adj[n][0]])
            return solve(adj[n][0]) + 1;
        else
            return 1;
    }
    if(adj[n].size() == 2 && (vis[adj[n][0]] ^ vis[adj[n][1]])) {
        return ( vis[adj[n][0]] ? solve(adj[n][1]) : solve(adj[n][0]) ) + 1;
    }

    int max1 = 0, max2 = 0, temp;
    for(auto c : adj[n]) {
        if(!vis[c]) {
            temp = solve(c);
            if (temp > max1) {
                max2 = max1;
                max1 = temp;
            } else if (temp > max2) {
                max2 = temp;
            }
        }
    }

    if (max1 + max2 + 1 > maxg) {
        maxg = max1 + max2 + 1;
    }

    return max1 + 1;
}

void print(int res) {
    ofstream out(OUTPUT);

    if(res > maxg)
        out << res;
    else
        out << maxg;

    out.close();
}



int main() {
    auto in = read();
    auto out = solve(in);
    print(out);

    return 0;
}