题目背景

zsh 正在 Minecraft 世界流浪！

他来到了一个神奇的、由许许多多村庄组成的神秘王国。这里的村庄与村庄之间存在着从属关系，村庄之间经济交流繁盛。

刚好，zsh 的末影箱里有很多绿宝石，他想与这里的村民们进行交易。不过，在交易之前，他想先了解一下这些村庄之间的贸易情况。

但是，这个王国实在是过于庞大，村庄数量非常多，zsh 自己计算不过来。所以，他找到了你来帮忙。

题目描述

这个王国里共有 $n$ 个村庄，每个村庄的编号分别为 $1\sim n$。每个村庄都会生产一种具有特定价值的物品，编号为 $i$ 的村庄生产的物品售价为 $w_{i}$ 颗绿宝石。除了最核心的村庄（也就是王国的国都所在地），每个村庄都有且仅有 $1$ 个上属村庄。上属村庄与下属村庄之间有 $1$ 条双向道路相连。

当 $2$ 个村庄所生产的物品售价之和不超过 $k$ 时，这 $2$ 个村庄之间就会建立 $1$ 种贸易关系。

现在 zsh 想知道，对于每一个村庄，在它的所有下属村庄（包括它自己以及间接的下属村庄）中，有多少对村庄之间建立了贸易关系。

输入格式

输入共 $n+1$ 行。

输入第 $1$ 行有 $2$ 个整数，分别表示 $n,k$（$n,k$ 的含义见题目描述）。

输入第 $2$ 行有 $n$ 个整数，第 $i$ 个整数表示编号为 $i$ 的村庄生产的物品售价 $w_{i}$ 颗绿宝石。

接下来 $n-1$ 行，每行有 $2$ 个整数 $u$ 和 $v$，表示编号为 $u$ 的村庄是编号为 $v$ 的村庄的上属村庄。

输出格式

输出共 $n$ 行，每行 $1$ 个整数。

第 $i$ 行的整数表示在编号为 $i$ 的村庄的所有下属村庄（包括它自己以及间接的下属村庄）中，建立的贸易关系的数量。

样例

4 5
1 3 2 4
1 2
1 3
2 4

4
0
0
0

说明/提示

【样例解释 #1】

村庄 $\left(1,2\right),\left(1,3\right),\left(1,4\right),\left(2,3\right)$ 之间会建立贸易关系，所以村庄 $1$ 的下属村庄中建立了 $4$ 种贸易关系；

而村庄 $2$ 的下属村庄 $2$ 和 $4$ 生产的物品售价之和为 $3+4=7>5$ 颗绿宝石，所以在村庄 $2$ 的下属村庄中没有贸易关系；

村庄 $3$ 和村庄 $4$ 没有除自己以外的下属村庄，所以在它们的下属村庄中没有贸易关系。

【样例 #2】

见附件下的 样例.zip/test2.in 与 样例.zip/test2.ans。
该样例满足测试点 $6\sim 15$ 的约束条件。

【样例 #3】

见附件下的 样例.zip/test3.in 与 样例.zip/test3.ans。
该样例满足测试点 $16\sim 23$ 的约束条件。

【样例 #4】

见附件下的 样例.zip/test4.in 与 样例.zip/test4.ans。
该样例满足测试点 $24\sim 31$ 的约束条件。

【样例 #5】

见附件下的 样例.zip/test5.in 与 样例.zip/test5.ans。
该样例满足测试点 $32\sim 35$ 的约束条件。

【样例 #6】

见附件下的 样例.zip/test6.in 与 样例.zip/test6.ans。
该样例满足测试点 $36\sim 50$ 的约束条件。

【数据范围与约束】

特殊性质 A：保证任意一个村庄最多只有一个直接相连的下属村庄。

特殊性质 B：保证所有村庄构成的从属关系是一棵完全二叉树。

特殊性质 C：保证对于所有 $1\le i\le n$，满足 $w_{i}\le\frac{k}{2}$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^{5},0\le w_{i}\le k< 2^{31}$。

附件

样例.zip