题目描述

小月有一棵包含 $n$ 个节点的树，节点的颜色用数组 $c_1,c_2,\dots,c_n$ 表示，节点 $i$ 的颜色为 $c_i$。 对于两个不同的节点 $u,v$，依次记录从 $u$ 到 $v$ 的简单路径上的所有节点。对于一条简单路径，每存在两个相邻节点的颜色不同，就记为一次换色。 请统计有多少个无序节点对 $\{u,v\}$ 满足：$c_u=c_v$，并且它们之间的路径恰好换色两次。无序节点对 $\{u,v\}$ 与 $\{v,u\}$ 视为同一个节点对。 【名词解释】 简单路径：树上任意两个节点之间的路径，不经过重复的点和边。在树上，任意两个节点间有且仅有一条简单路径。官方中文

输入格式

第一行输入一个整数 $n\left(1\leqq n\leqq 2\times 10^5\right)$，表示节点数量。 第二行输入 $n$ 个整数 $c_1,c_2,\dots,c_n\left(1\leqq c_i\leqq n\right)$，表示各节点的颜色。 此后 $n-1$ 行，每行输入两个整数 $u_i,v_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i\right)$，表示一条连接节点 $u_i$ 和 $v_i$ 的边。保证给出的是一棵树。官方中文

输出格式

输出一个整数，表示满足条件的无序节点对数量。官方中文