{"raw_statement":[{"iden":"background","content":"![](https://cdn.luogu.com.cn/upload/image_hosting/6205nazm.png)\n\n帆帆不满足于只构建一棵深蓝之树，他觉得深蓝之树只有深蓝色太单调了，于是想给这棵树染上颜色。"},{"iden":"statement","content":"由于现在已经来到了魔幻的龙年，帆帆的深蓝之树已经被染上了颜色，结点 $i$ 的颜色为 $a_i$。\n\n帆帆是一个喜新厌旧的人，在接下来的 $q$ 天中，他每天都会改变他喜欢的颜色，第 $i$ 天他喜欢的两种颜色是 $x_i,y_i$（$x_i\\neq y_i$）。\n\n但是为了照顾自己的树，他需要经常在树上移动，并且只会经过自己喜欢的颜色。\n\n具体来说，第 $i$ 天，帆帆会选择一个有序结点对 $(u,v)$，然后沿着 $u\\to v$ 的唯一简单路径移动，并且中间经过的结点（包含 $u,v$）颜色必须 $\\in \\{x_i,y_i\\}$（$u$ 可以等于 $v$），之后可以抽取一次宵宫。\n\n每一天你都需要抽取一个满命宵宫，然后告诉帆帆有多少种可能的选择有序结点对的方案。"},{"iden":"input","content":"第一行两个正整数 $n,q$。\n\n接下来一行 $n$ 个正整数 $a_1,a_2,\\cdots,a_n$ 表示每个点的颜色。\n\n接下来一行 $n-1$ 个正整数 $p_2,p_3,\\cdots,p_n$，表示对所有 $2\\le i\\le n$，树上存在一条边 $(p_i,i)$。\n\n接下来 $q$ 行，每行两个正整数 $x_i,y_i$。"},{"iden":"output","content":"对于每组询问输出一行一个正整数表示答案。"},{"iden":"note","content":"### 【样例 $1$ 解释】\n\n树的形态如图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/w65i5hof.png)\n\n对于第一组询问，合法的路径有且仅有 $\\{1,2,3\\}$ 中一点到另一点的路径。\n\n对于第二组询问，合法的路径有且仅有 $1\\to 1,1\\to 3,3\\to 1,3\\to 3,4\\to 4,5\\to 5$。\n\n### 【子任务约束】\n\n本题采用子任务捆绑测试。\n\n对于 $100\\%$ 的数据，有 $1\\le n\\le 10^6$，$1\\le q\\le 2\\times 10^6$，$1\\le a_i,x,y\\le n$，$x\\neq y$。保证 $p_i<i$。\n\n| 子任务编号 |        $n$         |        $q$         | 特殊性质 | 分值 | 依赖子任务 | \n| :--------: | :----------------: | :----------------: | :------: | :--: | :--: |\n| Subtask \\#1 |     $\\le 100$      |     $\\le 100$      |    无    | $7$  |无|\n| Subtask \\#2 |     $\\le 2000$     |     $\\le 2000$     |    无    | $18$ |$1$|\n| Subtask \\#3 |     $\\le 10^5$     | $\\le 2\\times 10^5$ |    A     | $5$  |无|\n| Subtask \\#4 |     $\\le 10^5$     | $\\le 2\\times 10^5$ |    B     | $19$ |无|\n| Subtask \\#5 |     $\\le 10^5$     | $\\le 2\\times 10^5$ |    无    | $21$ |$1,2,3,4$|\n| Subtask \\#6 | $\\le 2\\times 10^5$ | $\\le 5\\times 10^5$ |    无    | $10$ |$5$|\n| Subtask \\#7 | $\\le 10^6$ | $\\le 2\\times 10^6$ |    无    | $20$ |$6$|\n\n特殊性质 A：$p_i=1$。\n\n特殊性质 B：$p_i=i-1$。\n"}],"translated_statement":null,"sample_group":[["5 3\n1 2 1 3 3\n1 1 2 2\n1 2\n1 3\n2 3","9\n6\n9"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}