Migrated from Lutece 2960 树上计数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定一棵 $n$ 个结点的有根树和整数 $k$，每个点有一个非负点权 $a_i$，对于树上每一个点 $u$（$u$ 为这个点的编号），求满足 $\text{lca}(x,y)=u$ 且 $(a_x+a_y+u)\equiv 0\bmod k$ 的无序对 $(x,y)$ 数量。 此处 $\text{lca}(x,y)=u$ 表示 $x$与$y$的最近公共祖先为$u$。 编号从 $0$ 开始，树的根为 $0$ 号点。

Input

第一行两个整数 $n,k$，含义与题面相同。 第二行 $n$ 个整数，第 $i$ 个整数表示第 $i-1$ 号点的权值。 第三行 $n-1$ 个整数，第 $i$ 个数表示第 $i$ 号点的父结点的编号。

Output

$n$ 个整数，第 $i+1$ $(0 \leq i < n)$ 个数表示有多少个无序对 $(x,y)$，满足它们的最近公共祖先是 $i$，并且它们的点权之和加上 $i$ 的编号能够被 $k$ 整除。

Samples

6 2
0 1 0 1 0 1
0 0 1 1 2

6 2 1 0 1 0

Constraints

$1 \leq n \leq 10^6$ $1 \leq k \leq 10^6$ $0 \leq a_i <k$

Note

对于 $0$ 号点，满足的 $(x,y)$ 有：$(0,0),(0,2),(0,4),(2,4),(1,5),(3,5)$

由于数据较大，请注意读入方式。

提交的题解需要说明你的做法的复杂度。

Resources

2023 UESTC ICPC Training for Graph