### 问题描述 大衣由于被材料力学狠狠地折磨了，所以想出一棵材料力树来考验你。 给一棵包含 $N$ 个节点的树,节点$i$的颜色为 $A_i$，最初的根节点为 $1$ ,有 $Q​$ 组询问形式如下： - `1 u c`：将节点 $u$ 子树上的所有节点 $x$ 的颜色 $A_x$ 改为 $c$ 。 - `2 u`：将节点 $u​$ 作为新的根节点。 - `3 u c`：统计节点 $u$ 子树上所有颜色为 $c​$ 的节点个数，并输出答案。 你能通过大衣的考验吗？ ### 输入格式 第一行输入一个正整数 ​$N​$ 表示节点的个数。 第二行输入 $N$ 个整数 $A_1,A_2,\cdots,A_N​$ 表示节点的初始颜色。 接下来的 $N-1$ 行每行输入两个整数 $u,v​$ 表示树的一条边。 下一行输入一个正整数 $Q​$，表示询问的总个数。 接下来 $Q​$ 行表示询问，形式如题所示。 ### 输出格式 对每个形式 $3​$ 的询问输出一个整数表示答案，并换行。 ### 样例输入 ```text 6 1 2 1 1 3 3 1 2 2 3 2 4 1 5 4 6 7 3 2 1 1 4 2 3 2 2 2 6 3 2 2 1 1 4 3 2 1 ``` ### 样例输出 ```text 2 3 1 1 ``` ### 说明 - 询问 $1$：统计节点 $2$ 子树上颜色为 $1$ 的节点个数。 - 此时的根节点为 $1$，因此节点 $2$ 的子树包含节点 `{2,3,4,6}`。其中，节点 $3$ 和 $4$ 颜色都为 $1$，因此答案是 $2$。 - 询问 $2​$：把节点 $4​$ 子树中所有节点的颜色改为 $2​$。 - 现在节点 $4​$ 的子树包含节点 `{4,6}`。因此现在的颜色数组变为 `[1,2,1,2,3,2]`。 - 询问 $3​$：统计节点 $2​$ 子树上颜色为 $2​$ 的节点个数。 - 节点 $2,4,6$ 颜色为 $2$，所以答案是 $3$。 - 询问 $4$：将节点 $6$ 作为新的根节点。 - 询问 $5$：统计节点 $2$ 子树上颜色为 $2$ 的节点个数。 - 现在根节点为 $6$，因此子树 $2$ 包含 节点 `{1,2,3,5}`，其中，只有节点 $2$ 的颜色为 $2$，因此答案是 $1$。 - 询问 $6​$：把节点 $1​$ 子树中所有节点的颜色改为 $4​$。 - 现在节点 $1$ 的子树包含节点 `{1,5}`。因此现在的颜色数组变为 `[4,2,1,2,4,2]`。 - 询问 $7$：统计节点 $2$ 子树上颜色为 $1$ 的节点个数。 - 只有节点 $3$ 的颜色为 $1$，因此答案是 $1​$。 ### 评测数据规模 对于所有的评测数据，$1\le N,Q\le 2 \times 10^5$，$1\le A_i\le10^9$，$1\le u,v\le 2 \times 10^5$，$1\le type\le3，1\le u\le N，1\le c\le 10^9$。