Mise en place de la structure de données

Avant d'initier le processus récursif, il est impératif de construire correctement la topologie de l'arbre. Cela implique généralement de lire les relations de parenté et de stocker les successeurs de chaque sommet. Une étape préliminaire courante consiste à déterminer les propriétés statiques de chaque sous-arbre, telles que leur taille totale. Lorsque les entrées décrivent un ensemble de relations qui peuvent former une forêt plutôt qu'un unique arbre, il est recommandé d'introduire un nœud racine fictif pour unifier la structure.

L'implémentation privilégiée utilise souvent une exploration en profondeur (DFS) couplée à de la mémoïsation. Le flux de calcul descend vers les feuilles, remonte les valeurs agrégées et combine les états locaux pour former l'état du nœud courant.

Cas 1 : Maximisation pondérée avec contrainte de voisinage

Dans ce scénario classique, nous devons sélectionner un sous-ensemble maximal de nœuds pour optimiser un score total, sous réserve que deux sommets adjcaents ne puissent pas être sélectionnés simultanément. Chaque sommet possède une valeur associée.

Nous définissons deux états pour chaque nœud u : dp[u][0] représentant le gain maximum si u est exclu, et dp[u][1] si u est inclus. Les transitions s'effectuent selon que les enfants soient contraints ou libres.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

const int MAXN = 6005;
int val[MAXN];
int memo[MAXN][2];
bool visited[MAXN];
vector<int> adj[MAXN];
int num_nodes;

// Fonction de récursion pour calculer les états
int calculate_node(int u, bool included) {
    // Si déjà calculé, retourner la valeur stockée
    // Ici simplifié pour la lecture, dans une implémentation stricte ajouter une vérification de visite
    
    // Si feuille (pas d'enfant)
    if (adj[u].empty()) {
        return (included ? val[u] : 0);
    }

    int current_val = 0;
    
    if (included) {
        // Si j'inclus le nœud, je ne peux pas inclure les enfants
        current_val += val[u];
        for (int child : adj[u]) {
            current_val += calculate_node(child, false);
        }
    } else {
        // Si j'exclue le nœud, les enfants sont libres d'être inclus ou exclus
        for (int child : adj[u]) {
            int option_include = calculate_node(child, true);
            int option_exclude = calculate_node(child, false);
            current_val += max(option_include, option_exclude);
        }
    }
    return current_val;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> num_nodes;
    for (int i = 1; i <= num_nodes; ++i) {
        cin >> val[i];
    }
    
    int u_child, v_parent;
    for (int i = 0; i < num_nodes - 1; ++i) {
        cin >> u_child >> v_parent;
        adj[v_parent].push_back(u_child);
    }
    
    // Identifier la racine (celle qui n'a pas de parent dans ce graphe dirigé)
    vector<bool> has_parent(num_nodes + 1, false);
    for (int i = 1; i <= num_nodes; ++i) {
        for (int neighbor : adj[i]) {
            has_parent[neighbor] = true;
        }
    }
    
    int root = 1;
    for (int i = 1; i <= num_nodes; ++i) {
        if (!has_parent[i]) {
            root = i;
            break;
        }
    }
    
    cout << max(calculate_node(root, true), calculate_node(root, false)) << endl;
    
    return 0;
}</bool>

Cas 2 : Problème du sac à dos sur arbre

Cette variante introduit une contrainte globale sur le nombre d'arêtes ou de sous-nœuds que l'on peut conserver. Il s'agit d'un problème de fusion de sacs à dos où l'on doit décider combien de « ressources » allouer à chaque sous-arbre fils. Les arêtes possèdent des poids, et nous cherchons à maximiser la somme des poids tout en respectant une limite maximale de sélections.

L'approche nécessite deux boucles imbriquées lors de la remontée : une pour itérer sur les capacités actuelles disponibles, et une seconde pour répartir cette capacité entre le sous-arbre actuel et les autres enfants déjà traités.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>

using namespace std;

struct Edge {
    int dest;
    int weight;
};

const int LIMIT = 105;
int dp[LIMIT][LIMIT]; // dp[noude][edges_kept]
vector<Edge> tree_adj[LIMIT];
int subtree_size[LIMIT];
int n_nodes, k_edges;
bool processed[LIMIT];

void dfs_knapsack(int u) {
    subtree_size[u] = 1;
    dp[u][0] = 0;
    
    for (auto& edge : tree_adj[u]) {
        int v = edge.dest;
        int w = edge.weight;
        
        if (v == processed[u]) continue; 
        // Note: Dans une vraie implem bidirectionnelle, gérer le parent explicitement
        
        dfs_knapsack(v);
        
        // Fusion des états (SAC à DOS ARBORÉ)
        // On itère en arrière pour éviter de réutiliser la même arête plusieurs fois
        for (int i = min(k_edges, subtree_size[u]); i >= 0; --i) {
            for (int j = 1; j <= subtree_size[v] && i + j <= k_edges; ++j) {
                dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j - 1] + w);
            }
        }
        subtree_size[u] += subtree_size[v];
    }
}

// Simplification pour l'exemple : construction directe depuis entrée dirigée
void solve_apple_tree() {
    cin >> n_nodes >> k_edges;
    // Réduction de n car la racine ne compte pas comme branche à couper parfois
    // Selon spécification exacte du problème original
    
    for (int i = 0; i < n_nodes - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        // Supposons ici que u est parent de v pour simplifier l'exemple
        tree_adj[u].push_back({v, w});
    }
    
    dfs_knapsack(1);
    
    // Trouver le maximum valide pour exactement ou moins de k_edges
    int max_val = 0;
    for(int j=0; j<=k_edges; ++j) max_val = max(max_val, dp[1][j]);
    
    cout << max_val << endl;
}

int main() {
    solve_apple_tree();
    return 0;
}

Cas 3 : Gestion de dépendances et racines multiples

Lorsque les éléments ont des prérequis stricts, la structure résultante est une forêt (un ensemble d'arbres disjoints). Pour appliquer uniformément la technique précédente, on ajoute artificiellement une racine principale connectée à toutes les racines des arbres indépendants. Cette racine factice n'a aucune valeur mais permet de traiter l'ensemble comme un seul arbre enraciné.

Ici, la capacité représente le nombre maximum d'éléments choisis. Chaque élément choisi consomme 1 unité de capacité. Si un élément a des prérequis, sa sélection conditionne celle des descendants.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Course {
    int prerequisite;
    int credit_value;
};

const int MAX_C = 305;
int dp[MAX_C][MAX_C]; // dp[node][count_taken]
int sub_count[MAX_C];
vector<int> children[MAX_C];
Course courses[MAX_C];
int total_courses, allowed_selections;

void count_subtree(int u) {
    sub_count[u] = 1; // Compter le noeud lui-même
    for (int v : children[u]) {
        count_subtree(v);
        sub_count[u] += sub_count[v];
    }
}

void optimize_selection(int u, int limit) {
    // Initialisation base
    // Si c'est la racine factice (0), elle n'a pas de valeur propre
    if (u != 0) dp[u][1] = courses[u].credit_value;
    
    for (int v : children[u]) {
        optimize_selection(v, limit);
        
        // Boucle de fusion
        // Limite supérieure par la taille du sous-arbre et la capacité totale
        for (int i = min(limit, sub_count[u]); i >= 1; --i) {
             for (int j = 1; j <= sub_count[v] && i - j >= 1; ++j) {
                 dp[u][i] = max(dp[u][i], dp[u][i-j] + dp[v][j]);
             }
        }
        sub_count[u]++; // Mise à jour dynamique (optionnel selon implé)
    }
}

int main() {
    cin >> total_courses >> allowed_selections;
    
    for (int i = 1; i <= total_courses; ++i) {
        cin >> courses[i].prerequisite >> courses[i].credit_value;
        // Ajouter comme enfant du prérequis (0 si aucun prérequis)
        children[courses[i].prerequisite].push_back(i);
    }
    
    // Calcul initial des tailles pour optimiser les bornes des boucles
    count_subtree(0); 
    
    // Lancer l'optimisation depuis la racine factice 0
    // Capacité réelle permise est allowed_selections - 1 car la racine 0 est comptée dans l'allocation
    // Mais selon logique spécifique, on ajuste. Ici on prend directement m.
    
    optimize_selection(0, allowed_selections + 1);
    
    // Résultats stockés dans la racine factice
    cout << dp[0][allowed_selections + 1] << endl;
    
    return 0;
}