该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

B - 中档题

题目描述

给定一棵 $n$ 个点的有根树，树的根是 $1$ ，编号从 $1$ 到 $n$ ，边有边权，点有点权，设 $a_i$ 是点 $i$ 的点权。

设函数 $d$ 满足 $d(u,v)$ 等于 $u$ 到 $v$ 的简单路径上的边权之和。

现在会做 $q$ 次操作，每次给定 $x,y,v$ 三个数，我们首先将 $y$ 子树内的点的点权都加上 $v$ ，然后需要计算以下式子：

$\max\limits_{i=1}^n d(i,x)-a_i$ 。

你同时还要输出取到最大值的 $i$ 等于多少。如果存在多个这样的 $i$ ，输出最小的那个。

注意：每次操作做的修改是永久性的。

输入格式

第一行两个整数 $n,q$ ，分别代表点的个数和操作数。

第二行 $n$ 个整数，其中第 $i$ 个整数表示 $a_i$ 。

第 $3$ 行到第 $n+1$ 行中第 $i+1$ 行输入两个整数 $p_i,w_i$ ，表示 $i$ 的父亲是 $p_i$ ，且到 $p_i$ 的边权是 $w_i$ 。

接下来 $q$ 行，每行输入三个整数 $x,y,v$ ，表示一次操作。

输出格式

输出 $q$ 行，每行包含两个整数，分别表示最优值的对应下标，以及最优值。

样例

样例 1 输入

5 6
-10 0 2 -4 8 
1 7
1 1
2 2
2 -2
1 1 100
2 1 -100
1 1 0
4 3 10 
2 5 3
5 2 2

样例 1 输出

4 -87
1 17
4 13
1 19
1 17
1 15

更多样例

见下发文件。

数据范围

对于所有数据，$1\le n,q\le 2*10^5,1\le p_i<i,|a_i|\le 10^9,|w_i|\le 10^9,1\le x,y\le n,|v|\le 10^9$。

特殊性质 A：$\forall 2\le i\le n,p_i=i-1$ 。

特殊性质 B：$\forall 2\le i\le n,a_i\le 0,w_i\geq 0$ ；对于每次修改操作，$v\le 0$ 。

特殊性质 C：$\forall 2\le i\le n$ ，保证 $p_i$ 在 $[1,i-1]$ 间随机生成。