解题思路

给定一棵以 1 为根的树，每个节点有权值 $a_i$。对每个节点 $i$，要求统计在从根 1 到该节点 $i$ 的简单路径上，有多少无序对 $(x,y)$（$x\ne y$）满足 $a_x=a_y$。

核心做法：根到当前节点的前缀统计 + DFS（栈模拟）

• 沿着树做一次从根出发的 DFS。维护一张“当前路径上各权值出现次数”的表 freq，以及“当前路径上的相等权值对总数” pairs。

• 当进入一个节点 $u$ 时（把它加入根到当前的路径）：

  • 设该点的权值编号为 id，此权值在路径上已有次数为 c=freq[id]。

题目内容

Bingbong 有一棵 $n$ 个节点的树，编号为 $1$~ $n$ ，节点 $i$ 的权值为 $a_i$ 。

现在你需要计算对于任意的节点 $i∈|1,n|$ ，有多少对 $(x,y)(x≠y)$ ，满足 $x,y$ 两个节点均在 $1→i$ 的简单路径上，且 $a_x= a_y$ 。

输入描述

第一行一个数 $n(2≦n≦2×10^5)$ ，表示节点总数。

第二行 $n$ 个整数，表示节点 $i$ 的权值 $a_i(1≦n≦10^9)$ 。

接下来 $n-1$ 行，每行 $2$ 个整数 $u,v(1≦u,v≦n)$ ，表示当前无向边连接 $u,v$ 两个节点。

保证输入是一棵树。

输出描述

输出包含一行，共 $n$ 个整数，每个整数之同以空格隔开，含义如题所示。

样例1

输入

4
1 1 2 2
1 2
2 3
3 4

输出

0 1 1 2