第四次忍界大战

题号：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$ 是好路径，当且仅当

现在兜想知道这棵树上有多少条好路径，你能帮帮他吗？

第  行一个正整数 ，表示树的结点个数。
第  行  个空格隔开的正整数 ，表示每个结点的权值。
第  行到第  行，每行两个空格隔开的正整数 ，表示一条树边。

一个整数，表示树上好路径数。

示例1

复制

复制

总共  条简单路径，除了  和  这两条路径，其他都是满足要求的路径。

示例2

复制

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

复制

除了四条树边  各自贡献的两条简单路径外，还有  和  这两条简单路径。