#G1088. [GESP202412 七级] 燃烧

[GESP202412 七级] 燃烧

[GESP202412 七级] 燃烧

题目描述

小杨有一棵包含 nn 个节点的树,其中节点的编号从 11 到 nn。节点 ii 的权值为 aia_i。

小杨可以选择一个初始节点引燃,每个燃烧的节点会将其相邻节点中权值严格小于自身权值的节点也引燃,火焰会在节点间扩散直到不会有新的节点被引燃。

小杨想知道在合理选择初始节点的情况下,最多可以燃烧多少个节点。

输入格式

第一行包含一个正整数 nn,代表节点数量。

第二行包含 nn 个正整数 a1,a2,…,ana_1, a_2, \dots, a_n,代表节点权值。

之后 n−1n-1 行,每行包含两个正整数 ui,viu_i, v_i,代表存在一条连接节点 uiu_i 和 viv_i 的边。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

3

数据范围

子任务编号 数据点占比 nn
1 20% 1010
2 ≤100≤ 100
3 60% ≤105≤ 10^5
  • 对于全部数据,保证有 1≤n≤1051 ≤ n ≤ 10^5,1≤ai≤1061 ≤ a_i ≤ 10^6。