U233115 The Wilbur Soot DreamSMP Finale

> $\texttt{Wilbur：行吧，我坦白……你知道这个按钮是做什么的吗？}$ > $\texttt{Philza：嗯哼，我知道。}$ > $\texttt{Wilbur：你听过……墙上的这首歌吗？你之前听过吗？}$ > $\texttt{Wilbur：我想说，确实曾经有一个特别的地方，人们可以在那里——}$ > $\texttt{Wilbur：但它已经不复存在了，你明白吗？}$ > $\texttt{Philza：它还在啊，你们刚刚才夺回了它，Will……}$ > $\texttt{Wilbur：Phil 我真的差点就要按下去了！就差那么一点点！}$ > $\texttt{Wilbur：我已经来过大概七八次了，我来过，七八次了……}$ > $\texttt{（外面传来 Technoblade 的烟花弩声）}$ > $\texttt{Wilbur：他们在战斗，他们在战斗……}$ > $\texttt{Philza：而你只想把这一切都炸飞。}$ > $\texttt{Wilbur：是啊，我就是这么想的……我觉得，我——}$ > $\texttt{Philza：你们付出了那么多，才夺回这片土地，经历了那么多艰难困苦。}$ > $\texttt{Wilbur：我都不知道这按钮还能不能用了，我不知道这还管不管用。}$ > $\texttt{Wilbur：我可以就这么一按，我可以……}$ > $\texttt{Philza：你真的要冒这个险……}$ > $\texttt{Wilbur：曾经有人说过一句话，Phil，从一个叛徒的口中说出。}$ >$\texttt{Wilbur：}\overset{\texttt{IT WAS NEVER MEANT TO BE.}}{\texttt{这一切本不应该发生}}\texttt{。}$ >$\texttt{（Wilbur 的手按下了按钮）}$ 

给出一棵以 $1$ 号节点为根的树，一共包含 $n$ 个节点，每个节点有一个权值 $a_i$。 另外给出一个正整数 $p$，保证其为质数。 你需要求出对于每个 $i$，以 $i$ 号节点为根的子树中， 有多少个节点 $j$ 满足能在 $i$ 的子树中找到一个不为 $j$ 的节点 $k$，使得 $a_j \cdot a_k \equiv 1 \pmod p$。

第一行两个正整数 $n$ 和 $p$。 第二行共 $n$ 个正整数，第 $i$ 个数表示 $a_i$。 后面 $n-1$ 行，每行两个正整数 $u$ 和 $v$，表示 $u$ 号节点与 $v$ 号节点之间有一条边。

共 $n$ 行，第 $i$ 行表示以 $i$ 号节点为根的子树中所求值。

样例解释：  对于 $1$ 号节点，子树内有 $2,3,4,6$ 号节点成立。 对于 $2$ 号节点，子树内有 $2,6$ 号节点成立。 --- | $\texttt{测试点编号}$ | $n$ | | :----------: | :----------: | | $1 \sim 2$ | $1 \le n\le 10^2$ | | $3 \sim 4$ | $1 \le n\le 3\times 10^3$ | | $5 \sim 10$ | $1 \le n \le 10^5$ | 对于 $100\%$ 的数据，$1 \le n \le 10^5,1 \le a_i < p,p=99991$。