U378672 暴力写挂

## 请注意你的时间和空间常数

定义一个数对 $(i,j)$ 是好的当且仅当： $i\not= j\wedge\exist k\in N^*,\lfloor \frac{i}{k}\rfloor=j$ 给出一个大小为 $n$ 的树，值域 $m$，以及 $q$ 个询问。 树上第 $i$ 个点的权值为 $a_i$。 $1\le a_i \le m$。 对于每个询问，会给出询问路径 $(x,y)$ 。 查询有多少个 $i,j\in(x,y)$ 使得 $(a_i,a_j)$ 是好的。

第一行三个整数 $n,m,q$。 第二行 $n$ 个整数，第 $i$ 个数为 $a_i$。 接下来 $n-1$ 行，每行两个整数 $u,v$，表示树的一条边。 接下来 $q$ 行，每行两个整数 $x,y$，表示一次询问。

共 $q$ 行。 每行一个整数表示询问答案。

特殊性质 $A$：$u_i=i,v_i=i+1$ 特殊性质 $B$：保证树的形态随机。 | 子任务编号 | 分数 | $n,m,q\le$| 特殊性质| | :----------: | :----------: | :----------: | :----------: | |$1$|$5$|$100$|| |$2$|$10$|$500$|| |$3$|$10$|$2000$|| |$4$|$10$|$10000$|| |$5$|$20$|$50000$|$A$| |$6$|$15$|$50000$|$B$| |$7$|$30$|$50000$|| 空白为无特殊性质。 附加文件中的七个大样例分别满足七个子任务限制。