P1056树上查询（mock2query）

【题目描述】

小 S 正在整理一批层层归档的资料，小 N 则不断提出需要核对的范围。为了能够统一处理这些树上查询任务，小 S 将资料之间的层级关系整理成一棵以结点 $1$ 为根、共有 $n$ 个结点的有根树。

结点按照一次深度优先遍历中首次访问的顺序编号为 $1,2,\ldots,n$。因此，每个结点的子树中的结点编号构成一个连续区间，并且这个区间的左端点就是该结点本身。

每个结点 $i$ 有一个正整数权值 $w_i$。根结点的深度为 $1$，其余结点的深度等于其父亲结点的深度加 $1$。

对于任意非空连续区间 $[a,b]$，记 $w(a,b)=\sum_{i=a}^{b}w_i$，表示这个区间内所有结点的权值之和。

记 $d(a,b)=\operatorname{dep}\bigl(\operatorname{lca}(a,a+1,\ldots,b)\bigr)$，其中 $\operatorname{lca}(a,a+1,\ldots,b)$ 表示结点 $a,a+1,\ldots,b$ 的最近公共祖先，$\operatorname{dep}(u)$ 表示结点 $u$ 的深度。

小 N 共提出 $q$ 次查询。每次查询给出三个整数 $l,r,k$，要求小 S 在所有满足 $l\leq a\leq b\leq r$ 且 $w(a,b)\geq k$ 的连续区间 $[a,b]$ 中，求出 $d(a,b)$ 的最大值。

换言之，每次查询要求计算

保证每次查询均有 $k\leq w(l,r)$，因此至少存在一个满足条件的连续区间。

【输入格式】

从文件 $\textbf{\textit{query.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个正整数 $n,q$，分别表示树的结点数量与查询数量。

第二行包含 $n-1$ 个正整数 $p_2,p_3,\ldots,p_n$，其中 $p_i$ 表示结点 $i$ 的父亲结点。

第三行包含 $n$ 个正整数 $w_1,w_2,\ldots,w_n$，表示每个结点的权值。

接下来 $q$ 行，每行包含三个正整数 $l,r,k$，描述一次查询。

输入保证结点编号符合题目描述中的深度优先遍历顺序。

【输出格式】

输出到文件 $\textbf{\textit{query.out}}$ 中。

对于每次查询，输出一行一个正整数，表示满足条件的连续区间中 $d(a,b)$ 的最大值。

【样例 1 输入】

10 125 431 1 3 342 1 3 2 451 5 663 5 472 4 581 2 3

【样例 1 输出】

12233241

【说明/提示】

【样例 1 解释】

对于第一次查询，可以选择区间 $[3,5]$。该区间的权值之和为 $9$，其中所有结点的最近公共祖先为结点 $3$，深度为 $2$，因此答案为 $2$。

对于第二次查询，可以选择区间 $[5,5]$。结点 $5$ 的权值为 $4$，深度为 $3$，因此答案为 $3$。

【样例 2】

见选手目录下的 $\textbf{\textit{query/query2.in}}$ 和 $\textbf{\textit{query/query2.ans}}$。

该组样例符合测试点 $1\sim2$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{query/query3.in}}$ 和 $\textbf{\textit{query/query3.ans}}$。

该组样例符合测试点 $3\sim5$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{query/query4.in}}$ 和 $\textbf{\textit{query/query4.ans}}$。

该组样例符合测试点 $6\sim9$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{query/query5.in}}$ 和 $\textbf{\textit{query/query5.ans}}$。

该组样例符合测试点 $10\sim13$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{query/query6.in}}$ 和 $\textbf{\textit{query/query6.ans}}$。

该组样例符合测试点 $14\sim20$ 的数据范围。

【样例 7】

见选手目录下的 $\textbf{\textit{query/query7.in}}$ 和 $\textbf{\textit{query/query7.ans}}$。

该组样例符合测试点 $21\sim25$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq n,q\leq2\times10^5$，单个测试点内所有测试数据满足 $\sum n,\sum q\leq2\times10^5$。

特殊性质 A：对于所有 $2\leq i\leq n$，均有 $p_i=i-1$。

特殊性质 B：对于每次查询，均有 $k=w(l,r)$。

特殊性质 C：对于每次查询，均有 $k\leq\min_{i=l}^{r}w_i$。

对于所有测试数据，保证：

• $0\leq c\leq25$，$1\leq T\leq10$。
• 对于所有 $2\leq i\leq n$，均有 $1\leq p_i<i$。
• 对于所有 $1\leq i\leq n$，均有 $1\leq w_i\leq10^9$。
• 对于每次查询，均有 $1\leq l\leq r\leq n$，$1\leq k\leq w(l,r)$。