The Awesomest Vertex

题意翻译

给定一棵根为 $1$ 的有根树，每个节点有两个权值 $a[i]$ 和 $b[i]$ 。定义 $R(v)$ 为 $v$ 祖先的集合（包括自己），则一个节点 $v$ 有多棒取决于其真棒程度，真棒程度是这样定义的： $$ \left| \sum_{w \in R(v)} a_w \right| \cdot \left| \sum_{w \in R(v)} b_w \right|$$ $|x|$ 表示 $x$ 的绝对值。 现在请你支持两种操作： - $1 \ \ v \ \ x$ — 将 $a_v$ 加上 $x$ - $2 \ \ v$ — 输出以 $v$ 为根的子树中最大的真棒程度 数据范围： $1≤n≤2⋅10^5,1≤q≤10^5$ $ -5000≤a_i≤5000 \ ,-5000≤b_i≤5000 $ $ 1\leq x \leq 5000 $

题目描述

You are given a rooted tree on $ n $ vertices. The vertices are numbered from $ 1 $ to $ n $ ; the root is the vertex number $ 1 $ . Each vertex has two integers associated with it: $ a_i $ and $ b_i $ . We denote the set of all ancestors of $ v $ (including $ v $ itself) by $ R(v) $ . The awesomeness of a vertex $ v $ is defined as $ $\left| \sum_{w \in R(v)} a_w\right| \cdot \left|\sum_{w \in R(v)} b_w\right|, $ $ </p><p>where $ |x| $ denotes the absolute value of $ x $ . </p><p>Process $ q $ queries of one of the following forms: </p><ul> <li> <span class="tex-font-style-tt">1 v x</span> — increase $ a\_v $ by a positive integer $ x $ . </li><li> <span class="tex-font-style-tt">2 v</span> — report the maximum <span class="tex-font-style-it">awesomeness</span> in the subtree of vertex $ v$.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 1 \leq n \leq 2\cdot 10^5, 1 \leq q \leq 10^5 $ ) — the number of vertices in the tree and the number of queries, respectively. The second line contains $ n - 1 $ integers $ p_2, p_3, \dots, p_n $ ( $ 1 \leq p_i < i $ ), where $ p_i $ means that there is an edge between vertices $ i $ and $ p_i $ . The third line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ -5000 \leq a_i \leq 5000 $ ), the initial values of $ a_i $ for each vertex. The fourth line contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ -5000 \leq b_i \leq 5000 $ ), the values of $ b_i $ for each vertex. Each of the next $ q $ lines describes a query. It has one of the following forms: - 1 v x ( $ 1 \leq v \leq n $ , $ 1\leq x \leq 5000 $ ). - 2 v ( $ 1 \leq v \leq n $ ).

输出格式

For each query of the second type, print a single line with the maximum awesomeness in the respective subtree.

输入输出样例

输入样例 #1

5 6
1 1 2 2
10 -3 -7 -3 -10
10 3 9 3 6
2 1
2 2
1 2 6
2 1
1 2 5
2 1

输出样例 #1

100
91
169
240

说明

The initial awesomeness of the vertices is $ [100, 91, 57, 64, 57] $ . The most awesome vertex in the subtree of vertex $ 1 $ (the first query) is $ 1 $ , and the most awesome vertex in the subtree of vertex $ 2 $ (the second query) is $ 2 $ . After the first update (the third query), the awesomeness changes to $ [100, 169, 57, 160, 57] $ and thus the most awesome vertex in the whole tree (the fourth query) is now $ 2 $ . After the second update (the fifth query), the awesomeness becomes $ [100, 234, 57, 240, 152] $ , hence the most awesome vertex (the sixth query) is now $ 4 $ .