P6041 「ACOI2020」布丁暗杀计划

 茅野 カエデ（Kayano Kaede）制定了一个用布丁暗杀杀老师的计划。他们用剩余的鸡蛋加工制成一个布丁。为了外观和味道，他们会在里面加上一些用糯米纸包着的改变口味的食材。为了好看，这些食材从上至下排成了树的模样。在布丁的最底下铺满了 对老师炸弹 。杀老师吃到那里去之后就会引爆。

终于，同学们把布丁做好了。最爱吃布丁的茅野开始想，这个布丁有多好吃呢？ 一个布丁的好吃程度，取决于里面的改变口味的食材。材料不同的话，颜色和美味度也是不一样的。 布丁里面有 $n$ 种调味食材，有 $n-1$ 个东西连接着，第一种食材在最上面，相当于这一棵树的根。 现在，茅野制定一个布丁的好吃程度与指定的某两个值 $u,k$ 有关，这个好吃程度为，第 $u$ 种食材的 $k$ 级祖先 $v$ 食材的所有 $k$ 级儿子与 $v$ 食材颜色相同的那些 $k$ 级儿子的美味度之和。可以发现，$u$ 或者 $k$ 不同，一般情况下美味度是不同的。所以有 $q$ 个问题想要问你。 **特殊地，如果第 $u$ 种食材没有 $k$ 级祖先，直接输出 $0$ 即可。**

第一行两个整数 $n,q$，表示有 $n$ 个食材，$q$ 个询问。 第二行 $n$ 个整数，第 $i$ 个整数表示食材 $i$ 的颜色 $color_i$。 第三行 $n$ 个整数，第 $i$ 个整数表示食材 $i$ 的美味值 $d_i$。 第四行 $n-1$ 个整数，第 $i$ 个整数表示食材 $i+1$ 的父节点 $fa_i$。 接下来 $q$ 行，每行两个整数 $u,k$ 表示询问。

有 $q$ 行，每行一个整数，表示询问的结果。

#### 样例解释 #1  食材 $2$ 的 $1$ 级祖先是食材 $1$，食材 $1$ 的 $1$ 级儿子有食材 $2$ 与食材 $3$，食材 $2$ 与食材 $3$ 的颜色都与食材 $1$ 的颜色相同，所以美味度之和为 $2+3=5$。 ------------ #### 数据范围 **本题采用捆绑测试**。 - Subtask 1（30 points），鸡蛋缺乏，布丁不大：$n \leq 10^3$，$q \leq 10^4$。 - Subtask 2（20 points），食材构成了一条链：$n \leq 5 \times 10^5$，$q \leq 10^5$，$color_i \leq 10^2$。 - Subtask 3（50 points）：数据无特殊限制。 对于 $100\%$ 的数据，$1 \leq n,q,color_i \leq 5 \times 10^5$，$1 \leq d_i \leq 10^5$。 ------------ #### 提示 **第二个子任务中的测试点与第三个子任务中的测试点时限 2S。**