L. 数路径
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个根节点为 $$$1$$$ 的二叉树，点 $$$i$$$ 的权值为 $$$val_i$$$。求满足以下条件的路径 $$$a_1,a_2,\cdots, a_m$$$ 的数目：

  • 路径经过至少 $$$2$$$ 个点，即 $$$m\geq 2$$$
  • 路径上所有点的权值相等，即 $$$val_{a_1}=val_{a_2}=\cdots=val_{a_m}$$$
  • 对于 $$$1\leq i \lt m$$$，$$$a_{i+1}$$$ 为 $$$a_i$$$ 的一个孩子
Input

第一行 $$$1$$$ 个正整数 $$$n(1\leq n\leq 500)$$$，表示树的点数。

接下来一行 $$$n$$$ 个整数 $$$a_1,a_2,\cdots,a_n(1\leq a_i\leq n)$$$，表示每个点的点权。

接下来 $$$n$$$ 行，第 $$$i+2$$$ 行两个整数，表示点 $$$i$$$ 的左、右孩子编号（$$$0$$$ 表示不存在）。

Output

一行一个整数，表示满足条件的路径个数。

Example
Input
8
2 2 1 1 2 2 3 3
0 5
4 3
0 0
0 0
8 6
2 0
0 0
7 0
Output
7
Note

满足条件的路径如下：

  • $$$1,5$$$：权值都为 $$$2$$$
  • $$$1,5,6$$$：权值都为 $$$2$$$
  • $$$1,5,6,2$$$：权值都为 $$$2$$$
  • $$$5,6$$$：权值都为 $$$2$$$
  • $$$5,6,2$$$：权值都为 $$$2$$$
  • $$$6,2$$$：权值都为 $$$2$$$
  • $$$8,7$$$：权值都为 $$$3$$$

树的结构如下所示：