Somme de chemin à partir de la racine
On vous donne un arbre de
n nœuds, où le i-ème nœud possède une valeur (). Votre objectif est de déterminer le nombre de chemins dans cet arbre qui commencent au nœud racine et dont la somme est égale à une valeur donnée s.Entrée
La première ligne contient deux entiers séparés par un espace,
n et s (), qui représentent respectivement le nombre de nœuds dans l’arbre et la somme cible.
La deuxième ligne contient n entiers séparés par des espaces, à (), qui indiquent les valeurs attribuées à chaque nœud de l’arbre.
Les n-1 lignes suivantes décrivent les arêtes de l’arbre : chaque ligne contient deux entiers séparés par un espace, a et b (1 ≤ a, b ≤ n), représentant une arête entre les nœuds a et b. Il est garanti que ces arêtes forment un arbre.Sortie
Affichez un entier unique, qui correspond au nombre de chemins dans l’arbre partant du nœud racine et ayant pour somme la valeur
s.Exemples
Entrée | Sortie |
5 6
1 2 3 4 5
1 2
2 3
1 5
5 4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB