P10147 [Ynoi1999] 56TP


You are given a rooted tree with $n$ vertices. Each vertex $i$ has a weight $v(t,i)$ at time $t$. For each vertex, $v(0,i)$ is given. It is guaranteed that for any non-leaf node $i$, $v(0,i)=0$, and for any leaf node $i$, $0\le v(0,i)\le n$. There are $m$ queries. Each query gives $x,y,t$, asking for the minimum value, maximum value, and sum of the weights at time $t$ along the path from $x$ to $y$. For a leaf node $i$, $v(t,i)=v(0,i)$. For a non-leaf node $i$ with $t>0$, $v(t,i)$ is the maximum of $v(t-1,j)$ over all children $j$ of $i$.

The first line contains two integers $n,m$. The next $n-1$ lines each contain one integer, in order, representing $f_2,\dots,f_n$, where $f_i$ denotes the parent of node $i$, and the root is $1$. The next $n$ lines each contain one integer, in order, representing $v(0,1),v(0,2),\dots,v(0,n)$. The next $m$ lines each contain three integers representing $x,y,t$.

Output $m$ lines. Each line contains one integer, which is the answer to the corresponding query.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078. For $100\%$ of the testdata, $1\le n,m\le 10^6$, $1\le f_i\le i-1$, $0\le v(0,i)\le n$, $1\le x,y,t\le n$. Translated by ChatGPT 5