3276: 武器购买(GESP七级202412)

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n。节点 i 的权值为 aᵢ 。
小杨可以选择一个初始节点引燃,每个燃烧的节点会将其相邻节点中权值严格小于自身权值的在节点间扩散直到不会有新的节点被引燃。
小杨想知道在合理选择初始节点的情况下,最多可以燃烧多少个节点。

Input

第一行包含一个正整数 n ,表示节点数量。
第二行包含 n 个正整数 a₁ ,a₂ ,... ,aₙ ,代表节点权值。
之后 n-1 行,每行包含两个正整数 uᵢ ,vᵢ ,代表存在一条连接节点 uᵢ 和 vᵢ 的边。

Output

输出一个正整数,代表最多燃烧的节点个数。

Sample Input Copy

5
6 2 3 4 5
1 2
2 3
2 5
1 4

Sample Output Copy

3

HINT

数据范围:1≤n≤10⁵ ,0≤aᵢ≤10⁶