题目详情题解（0）讨论（0）提交记录（0）

AT_tkppc3_i.王国と M 種類の店

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

PAKEN 王国是一片由 NN 个顶点构成的树状结构。树中的每个顶点 ii（2≤i≤N2 \leq i \leq N）与顶点 PiP_i 通过一条长度为 LiL_i 的边相连。

在这个王国中，有 MM 种不同类型的商店，比如文具店、超市等（我们将它们称作为种类 11、种类 22、至种类 MM）。每个顶点上恰好有一家商店，且顶点 ii 上的商店类型为 RiR_i。

对于每个顶点 ii，我们定义其「不便度」为从顶点 ii 出发到达最近的各类型商店的最短距离总和，也就是到最近的种类 11 的商店的距离、加上到种类 22 的商店的距离，直至加上到种类 MM 的商店的最短距离。

你的任务是计算出顶点 11、顶点 22、一直到顶点 NN 这每一个顶点的「不便度」。

输入格式

输入包含以下内容，以标准输入形式给出：

  • 第一行两个整数 NN 和 MM，分别表示顶点数和商店种类数。
  • 第二行包含 N−1N-1 个整数，依次为 P2,P3,…,PNP_2, P_3, \ldots, P_N，表示边的起点。
  • 第三行包含 N−1N-1 个整数，依次为 L2,L3,…,LNL_2, L_3, \ldots, L_N，表示边的长度。
  • 第四行包含 NN 个整数，依次为 R1,R2,R3,…,RNR_1, R_2, R_3, \ldots, R_N，表示各顶点上的商店类型。

输出格式

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

输入输出样例

  • 输入#1

    5 2
1 2 1 2
3 5 2 4
2 1 2 1 1

    输出#1

    2
3
5
2
7

  • 输入#2

    10 3
1 2 3 3 1 6 7 8 8
2 3 5 3 1 1 6 2 7
1 3 2 2 3 2 3 1 1 3

    输出#2

    3
5
8
18
11
2
3
13
17
21

  • 输入#3

    5 5
1 2 3 4
1 2 3 4
1 2 3 4 5

    输出#3

    20
17
15
18
30

说明/提示

注意

每个测试用例的输入数据量较大，可能达到 7.5 MB7.5\ \text{MB}，因此在 C++ 中建议使用 scanf 和 printf 以替代 cin 和 cout。

制约

  • 1≤N≤400,0001 \leq N \leq 400,000
  • 1≤M≤400,0001 \leq M \leq 400,000
  • 1≤Pi≤i−11 \leq P_i \leq i - 1
  • 1≤Li≤1,000,0001 \leq L_i \leq 1,000,000
  • 1≤Ri≤M1 \leq R_i \leq M
  • 每种商店类型至少存在一个。

子任务

  1. 子任务 1 [ 5555 分 ]: N≤1,500N \leq 1,500，M≤750M \leq 750。
  2. 子任务 2 [ 110110 分 ]: N,M≤70,000N, M \leq 70,000 且 N=MN = M。
  3. 子任务 3 [ 275275 分 ]: N,M≤70,000N, M \leq 70,000 且每种商店类型最大仅有 88 个。
  4. 子任务 4 [ 330330 分 ]: N,M≤70,000N, M \leq 70,000。
  5. 子任务 5 [ 330330 分 ]: N,M≤400,000N, M \leq 400,000。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页