CF1178G The Awesomest Vertex

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|, $ $

where $ |x| $ denotes the absolute value of $ x $ .

Process $ q $ queries of one of the following forms:

• 1 v x — increase $ a\_v $ by a positive integer $ x $ .
• 2 v — report the maximum awesomeness in the subtree of vertex $ v$$$.

N/A

N/A

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 $ .