3925. 新建题目

【题目描述】

你有一棵 $n$ 个节点的树，每个点上有一个权值 $w_i$。节点 $1$ 为根。

一个点的深度 $dep_i$ 定义为根到该点的最短路径的边数。

定义一条简单路径是好的，当且仅当对于路径上任意两点 $x,y$，若 $dep_x>dep_y$ 则 $w_x>w_y$。

你需要计算出好的简单路径的数量。

【输入格式】

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，第 $i$ 个表示节点 $i$ 的权值 $w_i$。

接下来 $n-1$ 行，每行两个整数 $x,y$ 表示树的一条边 $(x,y)$。

【输出格式】

一个整数表示答案。

【样例输入1】

3
1 2 2
1 2
1 3

【样例输出1】

3

【样例输入2】

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

【样例输出2】

4

【样例说明2】

好的路径有：$(1,2),(2,4),(1,4),(5,6)$。

大样例

【数据规模与约定】

对于前 $40\%$ 的数据，保证 $1\le n \le 100$。

对于 $100\%$ 的数据，保证 $1\le n \le 2000,1\le w_i \le 10^9$。

【来源】

璃月港算法竞赛 T3.