神奇的炸鸡国

题号：NC231598
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

lzc，gjh和cwy一边吃着炸鸡，一边旅行。这一天他们来到了一个神奇的国度——炸鸡国。

炸鸡国一共有 $n$ 个人，这里个个都是人才，人人都会炸鸡，可以用 $a_i$ 来描述第 $i$ 个人的炸鸡水平。炸鸡国的统治结构是一颗树，通过 $n-1$ 条边连通。当确定了国王(即确定了树的根)时，可以得到一颗确定的有根树。

记 $f(u)$ 为 $u$ 的子树中炸鸡水平大于等于 $a_u$ 的总人数(不包含u本身)。

记 $g(u)$ 为以 $u$ 为根时， $\sum_{i=1}^nf(i)$ 的值。

请你输出 $g(1),g(2),g(3),...,g(n)$ 。

输入描述:

第一行包含一个正整数，表示炸鸡国的人数。

第二行包含个正整数，第个数为，表示第个人的炸鸡水平。

接下来行每行包含两个正整数和，表示和之间有一条边，保证无重边。

输出描述:

输出一行，包含个整数，第个整数表示。

示例1

输入

复制

输出

复制

2 2 1