AT_tkppc3_i 王国と M 種類の店

PAKEN 王国是一片由 $N$ 个顶点构成的树状结构。树中的每个顶点 $i$（$2 \leq i \leq N$）与顶点 $P_i$ 通过一条长度为 $L_i$ 的边相连。 在这个王国中，有 $M$ 种不同类型的商店，比如文具店、超市等（我们将它们称作为种类 $1$、种类 $2$、至种类 $M$）。每个顶点上恰好有一家商店，且顶点 $i$ 上的商店类型为 $R_i$。 对于每个顶点 $i$，我们定义其「不便度」为从顶点 $i$ 出发到达最近的各类型商店的最短距离总和，也就是到最近的种类 $1$ 的商店的距离、加上到种类 $2$ 的商店的距离，直至加上到种类 $M$ 的商店的最短距离。 你的任务是计算出顶点 $1$、顶点 $2$、一直到顶点 $N$ 这每一个顶点的「不便度」。

输入包含以下内容，以标准输入形式给出： - 第一行两个整数 $N$ 和 $M$，分别表示顶点数和商店种类数。 - 第二行包含 $N-1$ 个整数，依次为 $P_2, P_3, \ldots, P_N$，表示边的起点。 - 第三行包含 $N-1$ 个整数，依次为 $L_2, L_3, \ldots, L_N$，表示边的长度。 - 第四行包含 $N$ 个整数，依次为 $R_1, R_2, R_3, \ldots, R_N$，表示各顶点上的商店类型。

共输出 $N$ 行，每行一个整数，表示对应顶点的「不便度」。

### 注意 每个测试用例的输入数据量较大，可能达到 $7.5\ \text{MB}$，因此在 C++ 中建议使用 `scanf` 和 `printf` 以替代 `cin` 和 `cout`。 ### 制约 - $1 \leq N \leq 400,000$ - $1 \leq M \leq 400,000$ - $1 \leq P_i \leq i - 1$ - $1 \leq L_i \leq 1,000,000$ - $1 \leq R_i \leq M$ - 每种商店类型至少存在一个。 ### 子任务 1. 子任务 1 \[ $55$ 分 \]: $N \leq 1,500$，$M \leq 750$。 2. 子任务 2 \[ $110$ 分 \]: $N, M \leq 70,000$ 且 $N = M$。 3. 子任务 3 \[ $275$ 分 \]: $N, M \leq 70,000$ 且每种商店类型最大仅有 $8$ 个。 4. 子任务 4 \[ $330$ 分 \]: $N, M \leq 70,000$。 5. 子任务 5 \[ $330$ 分 \]: $N, M \leq 400,000$。 **本翻译由 AI 自动生成**