题目描述

小红拿到了—棵树，她定义路径的权值为路径上所有节点的权值之和。小红想知道，有多少条权值为3的路径? 我们定义，u -> v和v -> u为同—条路径。

输入描述

第—行输入—个正整数n，代表节点的数量；

第二行输入n个正整数ai，代表每个节点的权值；

接下来的n ― 1行，每行输入两个正整数u, v，代表节点u和节点v有一条路径连接。

1 <= n <= 100000;

1 <= ai <= 2;

1 <= u, v <= n.

输出描述

—个整数，代表权值为3的路径数量。

输入示例

3
1 2 1
1 2 
2 3

输出示例

2

提示信息

有两条路径满足条件，即节点1 -> 2, 2 -> 3。

时间限制：c/c++：1s；其他语言：4s。