// Una cadena de n nodos, primero sin recursión y luego con ella: deep_chain N. Se compila con -O2.
#include <cstdlib>
#include <iostream>
#include <vector>

#include "tree_dp.h"

int main(int argc, char* argv[]) {
    const int n = argc > 1 ? std::atoi(argv[1]) : 100000;
    RootedTree chain{std::vector<std::vector<int>>(static_cast<std::size_t>(n)), 0,
                     std::vector<long long>(static_cast<std::size_t>(n), 1)};
    for (int v = 0; v + 1 < n; v++) chain.children[v].push_back(v + 1);
    std::cout << "orden inverso de BFS, nodos bajo la raíz: " << subtree_sizes_bfs_order(chain.children, 0)[0] << std::endl;
    std::cout << "recursión, conjunto independiente: " << independent_set_value(chain) << std::endl;
}