Résoudre LeetCode jusqu'à ce que je devienne dans le top 1% — Jour `54`

Le problème consiste à trouver le score minimum après avoir supprimé deux arêtes d'un arbre avec n noeuds, où chaque noeud a une valeur. L'objectif est de minimiser la différence entre les valeurs XOR maximale et minimale des trois arbres séparés formés après avoir coupé les arêtes. Une approche par force brute consisterait à essayer toutes les paires d'arêtes possibles, mais cela aurait une complexité temporelle de O(n³). Une stratégie plus optimisée consiste à construire l'arbre à l'aide d'une liste d'adjacence et à effectuer une recherche en profondeur (DFS) à partir de la racine pour calculer la valeur XOR de sous-arbre pour chaque noeud et suivre les noeuds qui appartiennent au sous-arbre de chaque noeud. Ensuite, itérer sur chaque paire de noeuds, calculer les trois parties XOR et évaluer le score. Le score minimum trouvé est renvoyé. La mise en œuvre du code en Python utilise un defaultdict pour construire le graphe et une fonction DFS pour calculer la valeur XOR de sous-arbre et les descendants. La complexité temporelle et spatiale de la solution sont de O(n²). Les points clés à retenir du problème sont l'utilisation de XOR et de la programmation dynamique (DP) sur les arbres, ainsi que l'importance de comprendre les exigences du problème. L'auteur réfléchit à son expérience de résolution du problème, reconnaissant qu'il a eu besoin d'aide et qu'il n'a pas tout compris à la première fois.