#P18409. Fun on Tree

Fun on Tree

Fun on Tree

北投以美丽的风景和丰富的温泉闻名,吸引了许多希望放松身心的游客。温泉与水疗设施十分密集:这里曾是当地人享受天然温泉的安静山谷,如今已有三十多家豪华度假设施。

温泉通常让人想到火山活动,以及明显的硫磺气味。你恰好对这种气味敏感。游览北投时,你得到了一张地图;它可以表示为一棵有根树。这里的特殊环境甚至允许节点之间的距离为负数。每个节点还有一个硫磺含量值。

你发现原先的硫磺含量记录可能不准确,需要按照新情报不断修正。同时,情报还会指出附近最大火山的实际位置。你希望选一个离火山尽可能远、硫磺含量尽可能低的地点,评价值为“到火山的距离减去硫磺含量”。

具体地,树有 nn 个节点,编号 11 至 nn,根为 11。节点 jj 的当前硫磺含量是 aja_j。边权可以为负;两节点的距离是树上连接它们的唯一路径的边权和。

每条新情报给出三个整数 x,y,vx,y,v:

  1. 先把原根下 yy 的整棵子树(包含 yy)中每个节点的硫磺含量增加 vv。若 v<0v<0,表示含量减少。
  2. 最大火山现位于 xx。在全部节点 jj 中,找出使 dist⁡(x,j)−aj\operatorname{dist}(x,j)-a_j 最大的节点,并输出其编号和评价值。若有多个最优节点,选编号最小者。

修改会持续生效;后续情报不会撤销先前的硫磺含量修改。

输入格式

第一行包含两个整数 n,qn,q,满足 2≤n≤2⋅1052\le n\le2\cdot10^5,0≤q≤2⋅1050\le q\le2\cdot10^5。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n,满足 ∣ai∣≤109|a_i|\le10^9。

接下来 n−1n-1 行,第 ii 行(1≤i≤n−11\le i\le n-1)包含两个整数 pi+1,wi+1p_{i+1},w_{i+1},表示节点 i+1i+1 的父节点为 pi+1p_{i+1},这条边的权值为 wi+1w_{i+1}。满足 1≤pi+1≤i1\le p_{i+1}\le i,∣wi+1∣≤109|w_{i+1}|\le10^9。

接下来 qq 行,每行包含 x,y,vx,y,v,含义如上。满足 1≤x,y≤n1\le x,y\le n,∣v∣≤109|v|\le10^9。

输出格式

对每条新情报,输出一行两个整数 s,ds,d:最优节点的最小编号,以及其评价值。必须先应用本条修改,再计算本条答案。若 q=0q=0,不输出任何内容。

样例 1

6 6
1 1 4 5 1 4
1 5
2 0
3 2
4 1
5 6
3 2 -100000
1 2 100000
1 1 0
2 2 66
3 1 5
4 4 -3
6 100005
6 10
6 10
1 4
1 -1
1 1

样例 2

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
4 -87
1 17
4 13
1 19
1 17
1 15

样例 3

6 3
0 0 0 0 0 0
1 10
1 10
1 -100
4 10
4 11
1 1 0
4 1 0
1 4 1000
2 10
6 11
2 10