Background

Problem Description

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$.

Input Format

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 Format

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

8 3
1
2
3
3
3
4
4
0
0
0
0
7
5
7
5
7 5 8
1 2 8
8 2 8

7 7 28
7 7 14
5 7 26

Hint

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