题目思路

考虑树形dp，为每一个节点作为链的最高节点来代表其对应的最长链，其在链中前后的节点都是它的子节点，维护它对应链的链长。

由于它有前后两个方向，有两种类型的递增，所以共有4个状态，假设f[u][0], g[u][0]是分别是子节点权值大于等于节点u的链中前面节点对应的最长链长和次长链长，f[u][1], g[u][1]是分别是子节点权值小于等于节点u的链中前面节点对应的子链链长和后面节点对应的子链链长。

维护链长可以通过子节点的最长链来更新父节点的最长链和次长链（对应前和后），由于前面节点和后面节点不能是同一个，所以只需要子节点的最长链做更新即可。

初始时所有节点的链长都是1，然后从根节点开始dfs，更新链长，最后取最长链即可。

题意

给出几个点的树，节点编号为 1 到 n，根节点为 1，每个节点有一个权值。

我们想在这棵树上找一条最长的链，使得这个链上的节点均满足 $a_{f_n} <= a_i$ 或者均满足 $a_{f_n} >= a_i$，其中 $fa_i$ 表示的父亲节点，我们假定 $fa_1 = 1$。

输出这个最长链的节点数。

输入描述

第一行输入一个整数 $n(1 \leq n \leq 10^5)$代表树上的节点个数。

第二行输入 n 个整数 $a_1, a_2, \cdots, a_n(1 \leq a_i \leq 10^5)$代表每一个节点的权值。

此后 n-1 行，每行输入两个整数 $u_i$ 和 $v_i(1 \leq u_i, v_i \leq n; u_i \neq v_i)$表示树上第 i 条边连接节点 $u_i$ 和 $v_i$。保证树是联通的，没有重边。

输出描述

在一行上输出一个整数代表最长链的节点个数。

示例

输入：

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

输出：

5

解释：最长的链是 3 → 2 → 1 → 4 → 5。