Cod sursa(job #2779952)

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

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

using namespace std;

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

int maxg;
unordered_map<int, vector<int>> adj;

int read() {
    ifstream in(INPUT);

    int a, b, n;

    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) {

    if(adj[n].empty()) {
        return 1;
    }

    int max1 = 0, max2 = 0, temp;
    for(int c : adj[n]) {
        auto it = remove(adj[c].begin(), adj[c].end(), n);
        adj[c].erase(it, adj[c].end());


        temp = solve(c);

        if (temp > max1) {
            max2 = max1;
            max1 = temp;
        } else if (temp > max2) {
            max2 = temp;
        }
    }

    maxg = max(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;
}