P16691 怅惘 Plus

我该如何迎接希望？我问我自己。 > he- he- hello sunshine > > bye bye say bye to the night > > ——洛天依《hello&bye,days》

小 Z 得到了一棵树！ 这棵树共有 $N$ 个结点，编号为 $1,2,\dots,N$，以 $1$ 号结点为根。根的深度是 $1$，每一个结点的**深度**定义为**该节点到 $1$ 号根节点的简单路径上的边数加 $1$**。对于 $1 \le i \le N$，$i$ 号节点有一个权值 $A_i$。令 $D$ 为树的深度。 定义 $F(num_1,num_2)$ 为 $num_1$ 号结点对应的子树中深度为 $num_2$ 的结点权值的**可重集合**。 需要注意的是，这里深度的定义如第一段所描述，指的是以节点 $1$ 为根的深度，而非以节点 $num_1$ 为根。 特别地，若不存在 $num_1$ 号结点对应的子树中不存在深度 $num_2$，则 $F(num_1,num_2)=\emptyset$。 小 Z 会对你进行 $Q$ 次询问，每次询问给定两个正整数 $x$ 和 $d$，你需要计算有多少组 $(a,b)$ 满足以下条件： - $1 \le a \le N$，$1 \le b \le D$； - $(a,b) \neq (x,d)$； - $F(x,d)=F(a,b)$。

第一行包含两个正整数 $N$ 和 $Q$，分别表示树上结点的数量和询问的次数。 第二行包含 $N$ 个非负整数 $A_i$，表示每个结点的权值。 接下来 $N-1$ 行，每行两个正整数 $u$ 和 $v$，表示 $u$ 号结点和 $v$ 号结点之间存在一条边。 接下来 $Q$ 行，每行两个正整数 $x$ 和 $d$，表示询问的内容，含义见题目描述。

对于每次询问，包含一行一个非负整数，表示答案。

对于 $100\%$ 的数据，保证 $1 \le N,Q \le 10^5$，$1 \le A_i \le 10^5$，$1 \le u,v \le N$，$1 \le u \le N$，$1 \le d \le D$。