Tranche Belle#523

Tranche Belle

1,5 seconde
256 mégaoctets
Very hard

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 :

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 :

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 !

Input

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.

Output

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.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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

Scoring

  1. ( points) : a_i = 1 pour tous les ;

  2. ( points) : u_i = i ; v_i = i+1 ;

  3. ( points) : n \le 50 ;

  4. ( points) : n \le 10^3 ;

  5. ( points) : n = 2^k-1 ; u_i = \lfloor \frac{i+1}{2} \rfloor ; v_i = i+1 ;

  6. ( points) : pas de contraintes supplémentaires.