P11378 · \([GESP202412 七级]\) 燃烧

题意概述

给定一棵包含 \(n\) 个节点的无向树（节点编号 \(1\ldots n\)），第 \(i\) 个节点的权值为 \(a_i\)。 你可以任选一个节点作为初始火源点燃；之后火焰按如下规则在树上扩散：

• 若节点 \(u\) 已点燃，则它会使相邻且权值严格小于它的节点 \(v\) 点燃（即 \(a_v<a_u\)）。
• 扩散可以多轮进行，直到没有新的节点被点燃为止。

求：通过最优选择初始节点，最多能点燃多少个节点。

输入格式

• 第一行：一个整数 \(n\) —— 节点数。
• 第二行：\(n\) 个整数 \(a_1,a_2,\dots,a_n\) —— 各节点权值。
• 接下来 \(n-1\) 行：每行两个整数 \(u_i,v_i\)，表示在节点 \(u_i\) 与 \(v_i\) 之间有一条无向边。

输出格式

输出一个整数，表示在最优起点下，最终能被点燃的最大节点数。

样例

输入

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

输出

3

说明与约束

• \(1\le n\le 10^5\)
• \(1\le a_i\le 10^6\)
• 输入保证是一棵树（恰有 \(n-1\) 条无向边）
• 扩散只允许沿"权值严格下降"的相邻边进行；若两点权值相等则不会触发点燃。