第四次忍界大战
题号:NC296347
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

奥比土帮小 Z 做完手术后,又联合兜正式发动第四次忍界大战。
可以把战场地图近似为一棵 n 个结点的树,现在兜在 1 号结点,他发现每个结点都有一个权值 w_i

兜现在想让白绝走一些好路径,使得他们能够更快地加入战场。

我们称一个以 u 开始、以 v 结束的树上简单路径 s 是好路径,当且仅当
  • w_u = w_v
  • \forall i \in (1, |s|),均有 w_{s_i} > w_u,其中 |s| 表示路径中的结点个数;
  • |s| \geq 2
现在兜想知道这棵树上有多少条好路径,你能帮帮他吗?

输入描述:

1 行一个正整数 n \ (1 \leq n \leq 10^5),表示树的结点个数。
2n 个空格隔开的正整数 w_i \ (1 \leq w_i \leq 10^9),表示每个结点的权值。
3 行到第 n + 1 行,每行两个空格隔开的正整数 u, v \ (1 \leq u, v \leq n),表示一条树边。

输出描述:

一个整数,表示树上好路径数。
示例1

输入

复制
3
1 1 1
1 2
2 3

输出

复制
4

说明

总共 6 条简单路径,除了 1-2-33-2-1 这两条路径,其他都是满足要求的路径。
示例2

输入

复制
7
1 2 1 2 1 2 1
1 2
1 3
2 4
3 5
4 6
4 7

输出

复制
10

说明

除了四条树边 (1,3), \ (3, 5), \ (2, 4), \ (4, 6) 各自贡献的两条简单路径外,还有 1-2-4-7 和 7-4-2-1 这两条简单路径。