#P18409. Fun on Tree
Fun on Tree
Fun on Tree
北投以美丽的风景和丰富的温泉闻名,吸引了许多希望放松身心的游客。温泉与水疗设施十分密集:这里曾是当地人享受天然温泉的安静山谷,如今已有三十多家豪华度假设施。
温泉通常让人想到火山活动,以及明显的硫磺气味。你恰好对这种气味敏感。游览北投时,你得到了一张地图;它可以表示为一棵有根树。这里的特殊环境甚至允许节点之间的距离为负数。每个节点还有一个硫磺含量值。
你发现原先的硫磺含量记录可能不准确,需要按照新情报不断修正。同时,情报还会指出附近最大火山的实际位置。你希望选一个离火山尽可能远、硫磺含量尽可能低的地点,评价值为“到火山的距离减去硫磺含量”。
具体地,树有 个节点,编号 至 ,根为 。节点 的当前硫磺含量是 。边权可以为负;两节点的距离是树上连接它们的唯一路径的边权和。
每条新情报给出三个整数 :
- 先把原根下 的整棵子树(包含 )中每个节点的硫磺含量增加 。若 ,表示含量减少。
- 最大火山现位于 。在全部节点 中,找出使 最大的节点,并输出其编号和评价值。若有多个最优节点,选编号最小者。
修改会持续生效;后续情报不会撤销先前的硫磺含量修改。
输入格式
第一行包含两个整数 ,满足 ,。
第二行包含 个整数 ,满足 。
接下来 行,第 行()包含两个整数 ,表示节点 的父节点为 ,这条边的权值为 。满足 ,。
接下来 行,每行包含 ,含义如上。满足 ,。
输出格式
对每条新情报,输出一行两个整数 :最优节点的最小编号,以及其评价值。必须先应用本条修改,再计算本条答案。若 ,不输出任何内容。
样例 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