On a un groupe de combattants organisés en un arbre, où chaque combattant a un maître (sauf le chef). Chaque combattant a une certaine puissance de combat. Le but est d'inviter certains combattants pour maximiser la somme de leur puissance, tout en respectant la contrainte que si un maître est invité, aucun de ses disciples ne peut l'être.

Format d'entrée

• Première ligne : Un entier n (1 ≤ n ≤ 6000) représentant le nombre de combattants.
• Lignes 2 à n+1 : La puissance de combat de chaque combattant (entre -128 et 127).
• Lignes n+2 à 2n+1 : Paires d'entiers x y indiquant que y est le maître de x.
• Dernière ligne : 0 0 pour marquer la fin des paires.

Format de sortie

Un entier représentant la somme maximale de la puissance de combat des combattants invités.

Exemple

Entrée

3
52
42
36
1 3
3 2
0 0

Sortie

94

Approche

Le problème se résout en utilisant un algorithme de programmation dynamique sur un arbre (DP). On utilise un tableau bidimensionnel dp[i][j] où i est un combattant et j est un booléen indiquant si le combattant i est invité (1) ou non (0).

La relation de récurrence est la suivante : - Si le combattant i est invité, alors ses disciples ne peuvent pas l'être. - Si le combattant i n'est pas invité, alors ses disciples peuvent être invités. Le code implémente cette logique en parcourant l'arbre et en calculant la valeur maximale pour chaque sous-arbre.

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10000 + 50;

struct Edge {
    int next, to;
} e[maxn];

int dp[maxn][2];
int power[maxn];
int inDegree[maxn];
int head[maxn];
int cnt = 0;
int n, x, y, root;

void addEdge(int u, int v) {
    e[++cnt].next = head[u];
    head[u] = cnt;
    e[cnt].to = v;
    inDegree[v]++;
}

int dfs(int current, bool include) {
    if (!head[current]) {
        return include ? power[current] : 0;
    }
    for (int i = head[current]; i; i = e[i].next) {
        dp[current][include] += dfs(e[i].to, !include);
    }
    return dp[current][include];
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &power[i]);
    }
    for (int i = 1; i <= n; i++) {
        dp[i][1] = max(power[i], 0);
    }
    for (int i = 1; i < n; i++) {
        scanf("%d %d", &x, &y);
        addEdge(y, x);
    }
    scanf("%d %d", &x, &y);
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            root = i;
            break;
        }
    }
    dfs(root, 0);
    dfs(root, 1);
    printf("%d\n", max(dp[root][0], dp[root][1]));
    return 0;
}