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

As the competition was nearing its end, a banquet was held. For decoration, there was a tree with $n$ light bulbs numbered from $1$ to $n$ on it, where the $i$-th bulb has a $\textit{beauty}$ of $w_i$. The bulbs are connected by $n - 1$ circuits. Specifically, for each $i$ from $2$ to $n$, there is a circuit connecting the $i$-th bulb and the $f_i$-th bulb ($1 \leq f_i < i$). There is a row of $m$ switches that control the bulbs' lighting. Pressing the $i$-th switch toggles the state of all bulbs on the simple path from bulb $1$ to bulb $o_i$ on the tree (i.e., bulbs that are on turn off, and those that are off turn on). $q$ children will interact with the tree. The process for the $i$-th child is described by three integers $l_i$, $r_i$, and $x_i$: - Initially, all bulbs are off. - Then, the switches from the $l_i$-th to the $r_i$-th are pressed in sequence. - Finally, a photo is taken of the bulbs on the simple path from $1$ to $x_i$. The $\textit{total beauty}$ of a photo is the sum of the $\textit{beauty}$ of all bulbs that are on in the photo. Your task is to compute this value for each of the $q$ children.

The first line of the input contains three integers $n$, $m$, and $q$ ($1 \leq n, m, q \leq 5 \cdot 10^5$), where $n$ is the number of bulbs, $m$ is the number of switches, and $q$ is the number of children. The second line of the input contains $n-1$ integers $f_2, f_3, \ldots, f_n$ ($1 \leq f_i < i$), where $f_i$ represents a circuit between the $i$-th bulb and the $f_i$-th bulb. The third line of the input contains $n$ integers $w_1, w_2, \ldots, w_n$ ($0 \leq w_i \leq 1000$), where $w_i$ is the \textit{beauty} of the $i$-th bulb. The next $m$ lines of the input describe the switches. The $i$-th line of these contains a single integer $o_i$ ($1 \leq o_i \leq n$). The next $q$ lines of the input describe the interaction process of the children. The $i$-th line of these contains three integers $l_i$, $r_i$, and $x_i$ ($1\le l_i\le r_i\le m$, $1\le x_i\le n$).

Output $q$ lines, each containing an integer, representing the $\textit{total beauty}$ of each photo.

For the first child: - First, he pressed the first switch, causing the first and the second bulbs to turn on. - Then, he pressed the second switch, causing the first and the second bulbs to turn off while the third bulb turns on. - He took a photo of bulbs $1, 2, 3$, and $5$. In the photo, only the 3rd bulb was lit, resulting in a beauty of $48$.