Problem Background

In a hole in the ground there lived a hobbit. Not a nasty, dirty, wet hole, filled with the ends of worms and an oozy smell, nor yet a dry, bare, sandy hole with nothing in it to sit down on or to eat: it was a hobbit-hole, and that means comfort.

——Opening of "The Hobbit"

Problem Description

Brandy Hall is one of the largest hobbit holes, located inside the Buck Hill, and is the ancestral home of the Brandybucks. For centuries, the Brandybuck family has been expanding the size of Brandy Hall until it filled the entire hill. The Brandybucks are the maternal relatives of Frodo Baggins, who, at the age of twelve, was taken in by Brandy Hall after his parents drowned in a boating accident.

Brandy Hall has $n$ rooms connected by bidirectional circular passages. From any room, one can reach any other room, but to prevent getting lost in the maze-like passages, Brandy Hall is meticulously designed to ensure that there is only one path between any two rooms. In the hot summer, the Brandybucks have a tradition of storing sweet and delicious watermelons, but due to their large size, they store exactly one watermelon in each room. The sweetness of a watermelon is crucial, with the sweetness of the watermelon in room $i$ being $a_i$.

Frodo, being a guest, is free to roam around Brandy Hall and can stay overnight in any room he chooses. Each day, he travels from one room to another, always taking the shortest path. As he passes through each room, he can taste the watermelon there, though he may also choose to ignore it—including the rooms he starts and ends in.

Frodo loves sweet watermelons, but it is well known that the sweetness perceived by the taste buds is relative. That is, if Frodo eats a watermelon with sweetness $x$ and then another with sweetness $y$, his taste buds will only perceive the latter as sweet if $y > x$. If $y \le x$, he will not feel the sweetness of the latter. Therefore, Frodo has set a rule for himself: every watermelon he eats after the first one must be sweeter than the previous one.

One morning, Frodo suddenly felt tired of the monotonous life in Brandy Hall, and perhaps only watermelons could alleviate his boredom. He wanted to eat many watermelons without breaking his rule. Frodo began to ponder... He faces many choices every day: which room to start from, which room to end up in, which rooms' watermelons to eat and which to ignore... Frodo wonders, given all these choices, what is the maximum number of watermelons he can eat in a day?

Input Format

The first line contains a positive integer $n$, representing the number of rooms in Brandy Hall. It is guaranteed that $2 \le n \le 10^{5}$.

The second line contains $n$ positive integers, where the $i$-th integer $a_i$ represents the sweetness of the watermelon in room $i$. It is guaranteed that $1 \le a_i \le 10^{9}$.

The next $n - 1$ lines describe the structure of Brandy Hall. The $i$-th line contains two positive integers $u_i$ and $v_i$, indicating that there is a bidirectional passage between room $u_i$ and room $v_i$. It is guaranteed that $1 \le u_i, v_i \le n$.

Output Format

Output a single line containing a positive integer, which is the maximum number of watermelons Frodo can eat in a day.

Sample Input and Output

Sample Input #1

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

Sample Output #1

5

Sample Input #2

See the attached file 2.in.

Sample Output #2

See the attached file 2.ans.

Notes/Hints

[Sample Explanation #1]

The diagram below illustrates the structure of Brandy Hall in this sample case. The black lines represent the passages between rooms; the numbers on the left wall are the room numbers; the numbers inside the watermelons are their sweetness levels.

Frodo can eat a maximum of 5 watermelons in a day, with three possible choices to achieve this.

Choice One:

• Start from room 8 and eat the watermelon there (sweetness 1);
• Pass through room 6, ignoring the watermelon;
• Pass through room 1 and eat the watermelon there (sweetness 2);
• Pass through room 2 and eat the watermelon there (sweetness 4);
• Pass through room 4 and eat the watermelon there (sweetness 6);
• Arrive at room 5 and eat the watermelon there (sweetness 7).

Choice Two:

• Start from room 8 and eat the watermelon there (sweetness 1);
• Pass through room 6 and eat the watermelon there (sweetness 3);
• Pass through room 1, ignoring the watermelon;
• Pass through room 2 and eat the watermelon there (sweetness 4);
• Pass through room 4 and eat the watermelon there (sweetness 6);
• Arrive at room 5 and eat the watermelon there (sweetness 7).

Choice Three:

• Start from room 9 and eat the watermelon there (sweetness 2);
• Pass through room 6 and eat the watermelon there (sweetness 3);
• Pass through room 1, ignoring the watermelon;
• Pass through room 2 and eat the watermelon there (sweetness 4);
• Pass through room 4 and eat the watermelon there (sweetness 6);
• Arrive at room 5 and eat the watermelon there (sweetness 7).

[Subtasks]

This problem consists of multiple subtasks, each containing several test cases. A subtask's score is awarded only if all test cases in that subtask are passed.

The test cases in each subtask have specific constraints, as detailed in the table below:

For all test cases, it is guaranteed that $1 \le a_i \le 10^{9}$ and $2 \le n \le 10^{5}$.

Problem Usage Agreement

From the 2021 National High School Informatics Experience Camp at Tsinghua University (THUSC 2021).

The term "this repository" refers to the official THUSC 2021 repository (https://gitlink.org.cn/thusaa/thusc2021).

1. Any organization or individual may use or republish the problems in this repository for free.
2. Any organization or individual using the problems from this repository must do so without charge and openly. Profiting from these problems or adding special privileges to them is strictly prohibited.
3. If possible, please provide methods to obtain data, standard programs, and problem solutions when using these problems; otherwise, please include the repository's address.
4. The Department of Computer Science and Technology, Tsinghua University, reserves all rights.

见题面 Input 部分

见题面 Output 部分