P14451 [ICPC 2025 Xi'an R] Epilogue of Happiness

随着比赛接近尾声，举行了一场宴会。作为装饰，树上挂着 $n$ 个编号为 $1$ 到 $n$ 的灯泡，第 $i$ 个灯泡具有一个 **美丽值** $w_i$。这些灯泡通过 $n-1$ 条电路连接。具体而言，对于每个 $i$（$2 \leq i \leq n$），存在一条电路连接第 $i$ 个灯泡和第 $f_i$ 个灯泡（$1 \leq f_i < i$）。 有一排 $m$ 个开关控制这些灯泡的亮灭。按下第 $i$ 个开关，会切换从灯泡 $1$ 到灯泡 $o_i$ 这条简单路径上的所有灯泡的状态（即原本亮的灯泡会熄灭，原本灭的灯泡会点亮）。 接下来有 $q$ 个小朋友会与这棵树进行互动。第 $i$ 个小朋友的操作由三个整数 $l_i$、$r_i$ 和 $x_i$ 描述： - 起初，所有灯泡都是熄灭的； - 接着，依次按下第 $l_i$ 个到第 $r_i$ 个开关； - 最后，拍摄从灯泡 $1$ 到灯泡 $x_i$ 这条路径上所有灯泡的照片。 一张照片的 **总美丽值** 定义为照片中所有亮着的灯泡的 **美丽值** 之和。你的任务是计算每个小朋友拍摄的照片的总美丽值。

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$1 \leq n, m, q \leq 5 \cdot 10^5$），分别表示灯泡的数量、开关的数量以及小朋友的数量。 第二行包含 $n-1$ 个整数 $f_2, f_3, \ldots, f_n$（$1 \leq f_i < i$），其中 $f_i$ 表示存在一条电路连接第 $i$ 个灯泡和第 $f_i$ 个灯泡。 第三行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$0 \leq w_i \leq 1000$），其中 $w_i$ 表示第 $i$ 个灯泡的 **美丽值**。 接下来的 $m$ 行描述这些开关。第 $i$ 行包含一个整数 $o_i$（$1 \leq o_i \leq n$），表示第 $i$ 个开关控制的路径终点灯泡编号。 之后的 $q$ 行描述每个小朋友的互动过程。第 $i$ 行包含三个整数 $l_i$、$r_i$ 和 $x_i$（$1 \leq l_i \leq r_i \leq m$，$1 \leq x_i \leq n$）。

输出共 $q$ 行，每行包含一个整数，表示对应照片的 **总美丽值**。

对于第一个小朋友： - 首先，他按下第一个开关，使得第 1 个和第 2 个灯泡被点亮； - 接着，他按下第二个开关，使第 1 个和第 2 个灯泡熄灭，而第 3 个灯泡点亮； - 最后，他拍摄了从灯泡 $1$ 到灯泡 $5$ 的路径，也就是灯泡 $1, 2, 3, 5$。在照片中，只有第 3 个灯泡是亮的，因此总美丽值为 $48$。 翻译由 ChatGPT-5 完成