// Programación dinámica sobre árboles: conjunto independiente y cobertura de vértices con pesos.
#pragma once

#include <algorithm>
#include <cstddef>
#include <utility>
#include <vector>

// Un árbol con raíz, dado por las listas de hijos. Los ejemplos son chicos: aquí se usa recursión.
struct RootedTree {
    std::vector<std::vector<int>> children;
    int root;
    std::vector<long long> value;
};

struct TwoStates {
    std::vector<long long> with_node;     // lo mejor en el subárbol de v, con v dentro
    std::vector<long long> without_node;  // lo mejor en el subárbol de v, con v fuera
};

// Primero los hijos. Un nodo elegido obliga a sus hijos a quedar fuera; uno sin elegir los deja libres.
inline void fill_states(const RootedTree& tree, int v, TwoStates& s) {
    s.with_node[v] = tree.value[v];
    s.without_node[v] = 0;
    for (int c : tree.children[v]) {
        fill_states(tree, c, s);
        s.with_node[v] += s.without_node[c];
        s.without_node[v] += std::max(s.with_node[c], s.without_node[c]);
    }
}

inline TwoStates independent_set_states(const RootedTree& tree) {
    TwoStates s{std::vector<long long>(tree.value.size(), 0), std::vector<long long>(tree.value.size(), 0)};
    fill_states(tree, tree.root, s);
    return s;
}

inline long long independent_set_value(const RootedTree& tree) {
    const TwoStates s = independent_set_states(tree);
    return std::max(s.with_node[tree.root], s.without_node[tree.root]);
}

// De arriba hacia abajo: lo que se decide en un nodo depende de lo que se decidió en su padre.
inline void choose_down(const RootedTree& tree, const TwoStates& s, int v, bool parent_chosen, std::vector<int>& out) {
    const bool chosen = !parent_chosen && s.with_node[v] > s.without_node[v];
    if (chosen) out.push_back(v);
    for (int c : tree.children[v]) choose_down(tree, s, c, chosen, out);
}

inline std::vector<int> independent_set_nodes(const RootedTree& tree) {
    const TwoStates s = independent_set_states(tree);
    std::vector<int> out;
    choose_down(tree, s, tree.root, false, out);
    std::sort(out.begin(), out.end());
    return out;
}

// Error: mirar cada nodo por separado, sin preguntar qué se decidió en el padre.
inline std::vector<int> choose_each_node_alone(const RootedTree& tree) {
    const TwoStates s = independent_set_states(tree);
    std::vector<int> out;
    for (int v = 0; v < static_cast<int>(tree.value.size()); v++) {
        if (s.with_node[v] > s.without_node[v]) out.push_back(v);
    }
    return out;
}

// Error: un nodo sin elegir obliga a elegir a sus hijos.
inline std::pair<long long, long long> forced_children(const RootedTree& tree, int v) {
    long long with_v = tree.value[v];
    long long without_v = 0;
    for (int c : tree.children[v]) {
        const auto [with_c, without_c] = forced_children(tree, c);
        with_v += without_c;
        without_v += with_c;
    }
    return {with_v, without_v};
}

inline long long forced_children_value(const RootedTree& tree) {
    const auto [with_root, without_root] = forced_children(tree, tree.root);
    return std::max(with_root, without_root);
}

// Greedy que falla: los niveles pares o los impares, lo que sume más.
inline long long alternate_levels(const RootedTree& tree) {
    long long sum[2] = {0, 0};
    std::vector<std::pair<int, int>> stack = {{tree.root, 0}};
    while (!stack.empty()) {
        const auto [v, level] = stack.back();
        stack.pop_back();
        sum[level] += tree.value[v];
        for (int c : tree.children[v]) stack.push_back({c, 1 - level});
    }
    return std::max(sum[0], sum[1]);
}

// Greedy que falla: el de mayor valor primero, mientras no choque con un vecino ya elegido.
inline long long largest_value_first(const RootedTree& tree) {
    const int n = static_cast<int>(tree.value.size());
    std::vector<int> parent(tree.value.size(), -1);
    for (int v = 0; v < n; v++) {
        for (int c : tree.children[v]) parent[c] = v;
    }
    std::vector<int> order(tree.value.size());
    for (int v = 0; v < n; v++) order[v] = v;
    std::stable_sort(order.begin(), order.end(), [&tree](int x, int y) { return tree.value[x] > tree.value[y]; });
    std::vector<char> chosen(tree.value.size(), 0);
    long long total = 0;
    for (int v : order) {
        if (tree.value[v] <= 0) break;
        bool blocked = parent[v] != -1 && chosen[parent[v]];
        for (int c : tree.children[v]) blocked = blocked || chosen[c];
        if (!blocked) {
            chosen[v] = 1;
            total += tree.value[v];
        }
    }
    return total;
}

// Árbitro para árboles chicos: prueba los 2^n subconjuntos.
inline long long independent_set_brute(const RootedTree& tree) {
    const std::size_t n = tree.value.size();
    long long best = 0;
    for (unsigned mask = 0; mask < (1u << n); mask++) {
        bool ok = true;
        long long total = 0;
        for (std::size_t v = 0; v < n && ok; v++) {
            if (!(mask >> v & 1u)) continue;
            total += tree.value[v];
            for (int c : tree.children[v]) ok = ok && !(mask >> c & 1u);
        }
        if (ok) best = std::max(best, total);
    }
    return best;
}

inline long long min_cover_brute(const RootedTree& tree) {
    const std::size_t n = tree.value.size();
    long long best = 0;
    bool any = false;
    for (unsigned mask = 0; mask < (1u << n); mask++) {
        bool ok = true;
        long long total = 0;
        for (std::size_t v = 0; v < n && ok; v++) {
            if (mask >> v & 1u) total += tree.value[v];
            for (int c : tree.children[v]) ok = ok && ((mask >> v & 1u) || (mask >> c & 1u));
        }
        if (ok && (!any || total < best)) {
            best = total;
            any = true;
        }
    }
    return best;
}

// Cobertura de vértices de peso mínimo. El mismo patrón: un nodo fuera obliga a sus hijos a estar dentro.
inline std::pair<long long, long long> cover_states(const RootedTree& tree, int v) {
    long long inside = tree.value[v];
    long long outside = 0;
    for (int c : tree.children[v]) {
        const auto [inside_c, outside_c] = cover_states(tree, c);
        inside += std::min(inside_c, outside_c);
        outside += inside_c;
    }
    return {inside, outside};
}

inline long long min_cover_value(const RootedTree& tree) {
    const auto [inside, outside] = cover_states(tree, tree.root);
    return std::min(inside, outside);
}

// El orden inverso de BFS, en el cálculo más simple sobre un árbol: cuántos nodos tiene cada subárbol.
// Un padre sale siempre antes que sus hijos en un BFS, así que al revés cada nodo llega con sus hijos
// ya resueltos. No usa recursión, así que la profundidad del árbol no importa.
inline std::vector<int> subtree_sizes_bfs_order(const std::vector<std::vector<int>>& children, int root) {
    std::vector<int> parent(children.size(), -1);
    std::vector<int> order = {root};
    for (std::size_t t = 0; t < order.size(); t++) {
        for (int c : children[order[t]]) {
            parent[c] = order[t];
            order.push_back(c);
        }
    }
    std::vector<int> size(children.size(), 1);
    for (std::size_t t = order.size(); t-- > 1;) {
        size[parent[order[t]]] += size[order[t]];
    }
    return size;
}