// Conjunto independiente y cobertura en un árbol: dos estados, los errores y lo que pasa con un ciclo.
#include <iomanip>
#include <iostream>
#include <vector>

#include "tree_dp.h"

namespace {

void print_nodes(const std::vector<int>& nodes) {
    std::cout << '{';
    for (std::size_t i = 0; i < nodes.size(); i++) std::cout << (i ? ", " : "") << nodes[i];
    std::cout << '}';
}

void compare(const char* title, const RootedTree& tree) {
    std::cout << title << '\n';
    std::cout << "  fuerza bruta:              " << independent_set_brute(tree) << '\n';
    std::cout << "  dos estados:               " << independent_set_value(tree) << '\n';
    std::cout << "  niveles alternos:          " << alternate_levels(tree) << '\n';
    std::cout << "  mayor valor primero:       " << largest_value_first(tree) << '\n';
    std::cout << "  sin elegir obliga a hijos: " << forced_children_value(tree) << '\n';
}

}  // namespace

int main() {
    const RootedTree company{{{1, 2}, {3, 4}, {5}, {}, {}, {6, 7}, {}, {}}, 0, {4, 9, 6, 5, 5, 8, 3, 4}};
    std::cout << "Árbol: padre -> hijos\n";
    for (std::size_t v = 0; v < company.children.size(); v++) {
        std::cout << "  " << v << " (valor " << company.value[v] << ") ->";
        for (int c : company.children[v]) std::cout << ' ' << c;
        std::cout << '\n';
    }

    const TwoStates s = independent_set_states(company);
    std::cout << "\nnodo  valor   con  sin\n";
    for (std::size_t t = company.value.size(); t-- > 0;) {
        std::cout << std::setw(4) << t << std::setw(7) << company.value[t] << std::setw(6) << s.with_node[t]
                  << std::setw(5) << s.without_node[t] << '\n';
    }
    std::cout << "Mejor valor: " << independent_set_value(company) << ", con ";
    print_nodes(independent_set_nodes(company));
    std::cout << "\nCada nodo por separado, sin mirar al padre: ";
    print_nodes(choose_each_node_alone(company));
    std::cout << "\n\n";

    compare("El árbol de arriba:", company);
    const RootedTree chain{{{1}, {2}, {3}, {}}, 0, {10, 1, 1, 10}};
    compare("\nLa cadena 10, 1, 1, 10:", chain);
    const RootedTree star{{{1, 2, 3}, {}, {}, {}}, 0, {5, 2, 2, 2}};
    compare("\nUn jefe de valor 5 con tres personas de valor 2:", star);

    const RootedTree negative{{{1, 2}, {}, {}}, 0, {-4, -1, -2}};
    compare("\nTodos negativos:", negative);
    std::cout << "  elegidos: ";
    print_nodes(independent_set_nodes(negative));
    std::cout << '\n';

    long long total = 0;
    for (long long w : company.value) total += w;
    std::cout << "\nCobertura de peso mínimo del primer árbol\n";
    std::cout << "  con su propia recurrencia:         " << min_cover_value(company) << '\n';
    std::cout << "  fuerza bruta:                      " << min_cover_brute(company) << '\n';
    std::cout << "  total " << total << " menos conjunto independiente: " << total - independent_set_value(company) << '\n';

    // Un triángulo: el árbol de BFS desde 0 pierde la arista 1-2, y la cuenta ya no sirve.
    const RootedTree bfs_tree_of_triangle{{{1, 2}, {}, {}}, 0, {5, 5, 5}};
    std::cout << "\nUn triángulo con valores 5, 5, 5, usando el árbol de BFS desde 0\n";
    std::cout << "  el programa de árboles dice: " << independent_set_value(bfs_tree_of_triangle) << ", con ";
    print_nodes(independent_set_nodes(bfs_tree_of_triangle));
    std::cout << "\n  pero 1 y 2 son vecinos en el triángulo, y lo mejor de verdad es 5\n";
}