Representación de Árboles

¿Qué es un árbol?

Un árbol es un grafo conectado sin ciclos. Piénsalo como un árbol genealógico: hay un ancestro (raíz), sus hijos, los hijos de sus hijos (nietos), etc.

Propiedades clave:

• Un árbol con N nodos tiene exactamente N-1 aristas.
• Hay exactamente un camino entre cualquier par de nodos.
• Si quitas una arista, se desconecta. Si agregas una, creas un ciclo.

Terminología

        1        ← Raíz
       / \
      2   3      ← Hijos de 1
     /|    \
    4 5     6    ← Hojas: 4, 5, 6

Representación 1: Lista de adyacencia

La forma más común en competencias:

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100005;
vector<int> hijos[MAXN];
int padre[MAXN];

int main() {
    int n;
    cin >> n;

    // Leer n-1 aristas
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        hijos[u].push_back(v);
        hijos[v].push_back(u);
    }

    return 0;
}

Si no se especifica la raíz, el árbol se da como un grafo no dirigido y tú eliges la raíz (generalmente el nodo 1).

Representación 2: Padre de cada nodo

A veces el problema te da el padre de cada nodo directamente:

int padre[MAXN];

int main() {
    int n;
    cin >> n;

    // padre[i] = padre del nodo i
    for (int i = 2; i <= n; i++) {
        cin >> padre[i];
    }
    // padre[1] no existe (la raíz no tiene padre)
}

Representación 3: Hijos izquierdo y derecho (árbol binario)

Para árboles binarios (máximo 2 hijos por nodo):

struct Nodo {
    int valor;
    int izq, der;  // -1 si no existe
};

Nodo arbol[MAXN];

Calcular propiedades con DFS

Profundidad de cada nodo

int profundidad[MAXN];

void dfs(int nodo, int padre, int prof) {
    profundidad[nodo] = prof;

    for (int hijo : hijos[nodo]) {
        if (hijo != padre) {
            dfs(hijo, nodo, prof + 1);
        }
    }
}

// Llamar: dfs(1, 0, 0);

Tamaño de cada subárbol

int tam[MAXN];

void calcTam(int nodo, int padre) {
    tam[nodo] = 1;
    for (int hijo : hijos[nodo]) {
        if (hijo != padre) {
            calcTam(hijo, nodo);
            tam[nodo] += tam[hijo];
        }
    }
}

Altura del árbol

int altura(int nodo, int padre) {
    int maxH = 0;
    for (int hijo : hijos[nodo]) {
        if (hijo != padre) {
            maxH = max(maxH, 1 + altura(hijo, nodo));
        }
    }
    return maxH;
}

Diámetro del árbol

El diámetro es el camino más largo entre dos nodos del árbol. Se puede encontrar con dos BFS:

pair<int,int> bfsMasLejano(int inicio, int n) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    q.push(inicio);
    dist[inicio] = 0;

    int masLejano = inicio;
    while (!q.empty()) {
        int nodo = q.front(); q.pop();
        for (int v : hijos[nodo]) {
            if (dist[v] == -1) {
                dist[v] = dist[nodo] + 1;
                q.push(v);
                if (dist[v] > dist[masLejano]) masLejano = v;
            }
        }
    }

    return {masLejano, dist[masLejano]};
}

int diametro(int n) {
    auto [a, _] = bfsMasLejano(1, n);
    auto [b, d] = bfsMasLejano(a, n);
    return d;
}

Idea: Desde cualquier nodo, el más lejano es un extremo del diámetro. Desde ese extremo, el más lejano es el otro extremo.

Ejercicio de práctica

Dado un árbol con N nodos, encuentra la profundidad máxima (altura del árbol) con raíz en el nodo 1.

#include <iostream>
#include <vector>
using namespace std;

vector<int> adj[100005];

int altura(int nodo, int padre) {
    int maxH = 0;
    for (int hijo : adj[nodo]) {
        if (hijo != padre) {
            maxH = max(maxH, 1 + altura(hijo, nodo));
        }
    }
    return maxH;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cout << altura(1, 0) << endl;
    return 0;
}