← 返回题目列表

Codeforces · 490/F

F. 林地之旅

中文机器翻译题面 查看原题

“Road Accident”乐队正在计划在 Treeland 进行一场史无前例的巡演。 RA 的粉丝们非常期待这次活动,并打赌他们最喜欢的乐队将举办多少场演唱会。

Treeland由n个城市组成,一些城市对通过双向道路连接。总体而言,该国有 n-1 条道路。我们知道从任何一个城市到任何一个城市都是可能的。城市用 1 到 n 的整数编号。对于每个城市,我们都知道它的价值 ri——其中的人口数量。

我们知道乐队会沿着某条路径行进,在沿途的一些城市举办音乐会。乐队的路径不会经过一个城市两次,每次他们都会移动到以前没有访问过的城市。因此,音乐家将沿着某条路径旅行(不会两次访问任何城市),并在沿途的一些(不一定是全部)城市举办音乐会。

乐队计划在巡演期间聚集所有大型体育场和音乐厅,因此每次演出都会选择一个比之前访问过的演唱会城市人口更多的城市。也就是说,演唱会举办城市的人口序列是严格递增的。

在最近接受“道路事故”乐队领队采访时向歌迷承诺,乐队将在尽可能多的城市举办演唱会!这样乐队就会沿着Treeland的一些城市链旅行,并在其中一些城市举办音乐会,这样人口数量就会增加,音乐会的数量就会尽可能多。

Treeland 的粉丝们疯狂地想知道该乐队将在 Treeland 举办多少场演唱会。看起来如果没有真正的程序员的帮助他们就无法管理!帮助歌迷找到所需的演唱会数量。

输入

输入的第一行包含整数 n (2 ≤ n ≤ 6000) — Treeland 中的城市数量。下一行包含 n 个整数 r1, r2, ..., rn (1 ≤ ri ≤ 106),其中 ri 是第 i 个城市的人口。接下来的 n - 1 行包含道路的描述,每行一条道路。每条道路由一对整数 aj, bj (1 ≤ aj, bj ≤ n) 定义 - 由第 j 条道路连接的城市编号对。行中的所有数字均以空格分隔。

输出

打印“Road Accident”乐队将举办音乐会的城市数量。

示例

输入 #1

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

输出 #1

4

输入 #2

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

输出 #2

3