Monsieur IP a trouvé un graphe dans son jardin. Après quelques inspections, il s'est rendu compte que ce graphe est un arbre ! De plus, chaque sommet avait un paramètre de beauté a_i qui lui était attribué !
Il veut décorer sa chambre avec cet arbre, mais comme l'utiliser en entier peut être moche, il va le trancher en composants en procédant comme suit exactement une fois :
choisir un sommet dans l'arbre
retirer de l'arbre, laissant quelques composants connectés. Monsieur IP les utilisera pour décorer sa chambre.
Supposons qu'il reste composants après la tranche.
Nous définissons le centroïde d'un composant de taille comme étant le sommet avec la plus grande valeur de a_v parmi tous les sommets qui satisfont la propriété suivante :
si est retiré du composant, il se divise en composants plus petits de tailles au maximum \frac{m}{2}.
Soit c_1, c_2, \dots, c_k les centroïdes des composants résultants. La beauté d'une telle tranche est calculée comme la somme a_{c_1} + a_{c_2} + \dots + a_{c_k}.
Trouvez n'importe quel sommet qui maximise la beauté de la tranche, et calculez la beauté qu'il atteint !
La première ligne contient un entier (3 \le n \le 3 \cdot 10^5) — le nombre de sommets dans l'arbre.
La deuxième ligne contient entiers a_1, a_2, \dots, a_n (1 \le a_i \le 10^9) — les paramètres de beauté des sommets.
Les n-1 lignes suivantes contiennent la description de l'arbre : la i+2-ème ligne d'entrée contient deux entiers u_i et v_i (1 \le u_i, v_i \le n) — la -ème arête de l'arbre.
Il est garanti que l'entrée décrit un arbre valide.
Affichez deux entiers et — l'indice du sommet utilisé dans la tranche qui atteint la beauté maximale, et la valeur de la beauté de cette tranche.
Example 1
Example 2
Dans le premier exemple, pour chaque choix de sommet de "tranche" :
u = 1, les centroïdes des deux composants sont et , avec une beauté de 2+3 = 5.
u = 2, trois centroïdes sont , et , avec une beauté de 4+5+3 = 12.
u = 3, trois centroïdes sont , et , avec une beauté totale de 6+7+2 = 15.
Pour u=4,5, un seul centroïde est avec une beauté de .
Pour u=6,7, un seul centroïde est avec une beauté de .
Dans le deuxième exemple, en tranchant au sommet , trois composants sont formés : \{1\}, \{4\}, \{2,5,6\} avec les centroïdes et une beauté de 4+1+6=11
( points) : a_i = 1 pour tous les ;
( points) : u_i = i ; v_i = i+1 ;
( points) : n \le 50 ;
( points) : n \le 10^3 ;
( points) : n = 2^k-1 ; u_i = \lfloor \frac{i+1}{2} \rfloor ; v_i = i+1 ;
( points) : pas de contraintes supplémentaires.