Cod sursa(job #3360904)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 17 iulie 2026 15:10:42
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

const int MAX_N = 100000;

inline void maxSelf(int& x, int y)
{
    x = (x < y) ? y : x;
}

vector<int> adj[MAX_N + 1];
int n;

int toLeaf[MAX_N + 1],
    maxLength[MAX_N + 1];

void Read()
{
    f >> n;
    for(int i = 1; i < n; i++)
    {
        int a, b;
        f >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
}

void DFS(int node, int parent)
{
    for(int next : adj[node])
        if(parent != next)
        {
            DFS(next, node);
            maxSelf(toLeaf[node], toLeaf[next] + 1);
        }
    if(adj[node].empty())
        return;
    if((int)adj[node].size() <= 1)
    {
        maxSelf(maxLength[node], toLeaf[adj[node][0]] + 1);
        return;
    }
    int node1 = 0, node2 = 0;
    for(int next : adj[node])
        if(toLeaf[next] > toLeaf[node1])
        {
            node2 = node1;
            node1 = next;
        }
        else
        if(toLeaf[next] > toLeaf[node2])
            node2 = next;
    maxSelf(maxLength[node], toLeaf[node1] + toLeaf[node2] + 2);
}

void GetDiameter()
{
    int diam = 0;
    for(int i = 1; i <= n; i++)
        maxSelf(diam, maxLength[i]);
    g << diam + 1 << '\n';
}

int main()
{
    Read();
    DFS(1, -1);
    GetDiameter();

    f.close();
    g.close();

    return 0;
}