3774 - D - Determine the Superior

Created by Luis Manuel Díaz Barón & Frank Arteaga Salgado
Added by luismo (2017-04-05)
Limits
Total Time: 15000 MS | Test Time: 1000 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

You are given a tree of N nodes, with nodes numbered 1 to N and rooted at node 1. Each node has an integer value associated with it. We define a node as SUPERIOR if it has no ancestor or descendant with greater value than its own. Can you find the minimum value over all of the SUPERIOR nodes?
Dado un árbol de N nodos numerados de 1 a N donde la raíz es el nodo 1. Cada nodo tiene un valor entero asociado. Se define un nodo como SUPERIOR si este no tiene antecesores o descendientes con un valor mayor que el nodo. ¿Puedes encontrar el mínimo valor de todos los nodos SUPERIORES;jsessionid=C41CE79D6949FCC5D9536F73DAD61DBB?
You are given a tree of N nodes, with nodes numbered 1 to N and rooted at node 1. Each node has an integer value associated with it. We define a node as SUPERIOR if it has no ancestor or descendant with greater value than its own. Can you find the minimum value over all of the SUPERIOR nodes?

Input specification

In the first line a single integer N (1 ≤ N ≤ 105). The next line contains N space-separated integers Vi, where the ith value corresponds to the value of the ith node (1 ≤ Vi106). The next N - 1 lines contain two space separated integers A (1 ≤ A ≤ N) and B (1 ≤ B ≤ N), meaning that there is an edge between node A and node B.
La primera línea tiene un entero N (1 ≤ N ≤ 105). La línea siguiente contiene N enteros Vi separados por un espacio, donde el i-ésimo valor corresponde al valor del i-ésimo nodo, (1 ≤ Vi106). Las siguientes N - 1 líneas contienen dos enteros separados por un espacio A (1 ≤ A ≤ N) y B (1 ≤ B ≤ N), representando que existe una arista entre el nodo A y el nodo B.
In the first line a single integer N (1 ≤ N ≤ 105). The next line contains N space-separated integers Vi, where the ith value corresponds to the value of the ith node (1 ≤ Vi106). The next N - 1 lines contain two space separated integers A (1 ≤ A ≤ N) and B (1 ≤ B ≤ N), meaning that there is an edge between node A and node B.

Output specification

Print a single line containing the integer value of a SUPERIOR node which is minimum among all SUPERIOR nodes.
Imprima una sola línea con el valor entero del nodo SUPERIOR que corresponde al mínimo valor entre todos los nodos SUPERIORES.
In the first line a single integer N (1 ≤ N ≤ 105). The next line contains N space-separated integers Vi, where the ith value corresponds to the value of the ith node (1 ≤ Vi106). The next N - 1 lines contain two space separated integers A (1 ≤ A ≤ N) and B (1 ≤ B ≤ N), meaning that there is an edge between node A and node B.

Sample input

7
1 2 5 5 10 1 9
1 6
1 4
4 5
6 7
7 2
7 3

Sample output

9

Hint(s)

Sample input #2
5
5 8 8 4 3
1 5
5 2
1 3
5 4

Sample output #2
8
Sample input #2
5
5 8 8 4 3
1 5
5 2
1 3
5 4

Sample output #2
8
Sample input #2
5
5 8 8 4 3
1 5
5 2
1 3
5 4

Sample output #2
8