CF490F Treeland Tour

“Road Accident”乐队计划在 Treeland 展开一场空前绝后的巡回演出。RA 的粉丝们对此翘首以盼，并开始猜测他们心爱的乐队将在多少个城市举办音乐会。 Treeland 由 $n$ 个城市组成，部分城市之间由双向道路连接。全国共有 $n-1$ 条道路。已知从任意一个城市都可以到达其他任意城市。城市编号为 $1$ 到 $n$。每个城市有各自的人口数 $r_{i}$。 已知乐队将沿着某条路径旅行，并在路径上的部分城市举办音乐会。乐队的行进路线不会重复经过同一个城市，每次只能前往尚未访问过的城市。因此，乐队会沿着某条不重复经过城市的路径行进，并在路径上的部分（不一定全部）城市举办音乐会。 乐队计划演出时吸引所有最大的体育场和音乐厅，因此每次演出都会选择人口比上一次演出的城市更多的城市。换句话说，举办演出的城市人口数形成的序列是严格递增的。 在一次采访中，“Road Accident”乐队的主唱向粉丝们承诺，乐队将在尽可能多的城市举办音乐会！于是，乐队将沿着 Treeland 的某一条城市链行进，在其中部分城市举办音乐会，使得举办城市的人口数严格递增，并且演出的城市最多。 Treeland 的粉丝们疯狂地想弄清楚乐队将在多少个城市举办音乐会。看来他们急需一位真正的程序员帮忙！请帮粉丝们找出这个最大值。

第一行包含一个整数 $n\ (2 \leq n \leq 6000)$ —— Treeland 的城市数。 第二行包含 $n$ 个整数 $r_1, r_2, \cdots, r_n\ (1 \leq r_i \leq 10^6)$，其中 $r_i$ 表示第 $i$ 个城市的人口数。 接下来的 $n-1$ 行每行包含两个整数 $a_j, b_j\ (1 \leq a_j, b_j \leq n)$，表示第 $j$ 条道路连接第 $a_j$ 个和第 $b_j$ 个城市。各行中的数字均以空格分隔。

输出乐队最多能够举办音乐会的城市数量。

由 ChatGPT 5 翻译