[Ynoi1999] 56TP


给包含 $n$ 个顶点的有根树，每个顶点 $i$ 在时刻 $t$ 有权重 $v(t,i)$。 对每个顶点给出 $v(0,i)$，保证对非叶节点 $i$ 有 $v(0,i)=0$，对叶子 $i$ 有 $0\le v(0,i)\le n$。 共 $m$ 次询问，每次询问给出 $x,y,t$，问 $x$ 到 $y$ 路径上在时刻 $t$ 的权重的最小值、最大值、和。 对叶子 $i$，有 $v(t,i)=v(0,i)$； 对非叶节点 $i$，$t>0$，$v(t,i)$ 是 $i$ 的每个孩子 $j$ 的 $v(t-1,j)$ 的最大值。

第一行两个整数 $n,m$。 接下来 $n-1$ 行每行一个整数依次表示 $f_2,\dots,f_n$，其中 $f_i$ 表示节点 $i$ 的父亲，根为 $1$。 接下来 $n$ 行每行一个整数依次表示 $v(0,1),v(0,2),\dots,v(0,n)$。 接下来 $m$ 行，每行三个整数表示 $x,y,t$。

输出 $m$ 行，共 $m$ 个整数表示每个询问的答案。

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

Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078 对于 $100\%$ 的数据，满足 $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$。