4320. 树

单点时限: 8.0 sec

内存限制: 512 MB

有一棵 $n$ 个节点,以1号节点为根的有根树,每个节点有点权 $a_i$。

对于一个三元组 $(x,y,z)$,如果满足 $a_x+a_z=a_y$,并且 $x$ 是 $y$ 的祖先,$y$ 是 $z$ 的祖先,那么就称这个三元组是好的。

请你输出一共有多少好的三元组。

输入格式

第一行读入一个整数 $n$($1\le n \le 10^5$),表示树的节点个数。

第二行读入 $n$ 个整数 $a_1,\ a_2,\ \dots,\ a_n$($-60~000 \le a_i \le 60~000$),表示各个节点的点权。

接着 $n − 1$ 行,每行读入两个整数 $ x, y$,表示链接 $x$ 和 $y$ 的一条边。

输出格式

一个整数,表示答案。

样例

Input
5
1 5 4 3 2
1 2
2 3
1 4
4 5
Output
2

提示

两个三元组分别为 $(1,2,3)$ 和 $(1,4,5)$。

1 人解决,26 人已尝试。

1 份提交通过,共有 128 份提交。

9.9 EMB 奖励。

创建: 3 年,3 月前.

修改: 3 年,2 月前.

最后提交: 1 年,1 月前.

来源: N/A

题目标签