当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6843：Query on the Tree

题目描述
给你一棵有根树，节点的编号为$1,\ldots, n$，其中节点$1$为根。每个点有个点权$f_i$。对于任意一个点$i$，记$g_i$为这个点到根路径上所有点$f$的最大值。你要支持两个操作：

- `1 i v`，表示操作1：将$f_i$修改为$v$。
- `2 i`，表示操作2：求出$i$这个点在这个操作之前，每次操作之后$g_i$的值的和，这里的操作包括修改（操作1）和询问（操作2）。如果这个操作之前没有任何操作，那么和为$0$。

在最后，请对于每个点$i$输出它每次操作之后$g_i$值的和。
输入解释
第一行一个正整数$T(1\leq T\leq 2)$表示数据组数。

对于每组数据，第一行一个整数$n,q(1\leq n,q \leq 10^5)$，表示点数和操作个数。接下来一行$n-1$个整数$p_2, p_3, \dots, p_n (1\leq p_i < i-1)$，$p_i$表示第$i$个点的父亲。

接下来一行$n$个数$f_1, f_2, \dots, f_n(1\leq f_i\leq 10^9)$表示这$n$个点的初始权值。

接下来$q$行，每行一个形如`1 i v`$(1\leq i\leq n, 1\leq v\leq 10^9)$或者`2 i`$(1\leq i \leq n)$的操作，操作的含义见题目描述。
输出解释
对于每组数据，对于其中每个询问操作，输出一行，表示这个询问的答案。接下来按照$i$从$1$到$n$的顺序依次输出每个点$i$每次操作之后$g_i$值的和，每行一个数。
输入样例 
1
5 6
1 1 3 3
1 2 3 4 5
2 5
2 5
1 1 6
2 5
1 3 7
2 5
输出样例 
0
5
16
29
26
28
32
34
36
提示
每次操作之后g5的值依次为5, 5, 6, 6, 7, 7。
来自杭电HDUOJ的附加信息
Recommend heyang
该题目是Virtual Judge题目，来自 杭电HDUOJ
题目来源 2020 年百度之星·程序设计大赛 - 复赛
源链接： HDU-6843
最后修改于 2020-10-25T23:34:52+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
16000/8000MS(Java/Others) 524288/524288K(Java/Others)