题目描述

在一片兔窝中，有 $N$ 个相互连通的兔窝， $1$ 号洞是阿兔的窝（树的根节点）。

这些兔窝构成了一棵树形结构。每个兔窝都有一个舒适度值 $a_i (1 ≤ a_i ≤ N)$。作为兔窝的统计员，你需要为每个兔窝 $u$ 计算其子树中兔窝舒适度小于 $a_u$ 的数量。

输入格式

第一行包含一个整数 $N\ (1 ≤ N ≤ 2×10^5)$，表示兔窝的数量。

第二行包含 $N$ 个整数 $a_1, a_2, ..., a_N\ (1 ≤ a_i ≤ N)$，表示每个兔窝的舒适度。

接下来 $N-1$ 行，每行包含两个整数 $u$ 和 $v\ (1 ≤ u, v ≤ N)$，表示兔窝 $u$ 和 $v$ 之间有一条通道。保证输入的通道构成一棵树。

输出格式

输出 $N$ 个整数，第 $i$ 个整数表示兔窝 $i$ 的子树中舒适度小于 $a_i$ 的兔窝数量。

3
2 1 1
1 2
3 1

2 0 0

数据范围

• 对于 $100\%$ 的数据，$N ≤ 2×10^5$
• 保证所有舒适度 $1 ≤ a_i ≤ N$