The Awesomest Vertex
Contest: Codeforces Global Round 4
Difficulty rating: 3000
Tags: data structures, dfs and similar

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

Input format:
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$$$).

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

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
100
91
169
240

Editorial:
Denote $$$c_v = \sum_{w \in R(v)} a_w$$$ and $$$d_v = \sum_{w \in R(v)} b_w$$$.
Let's solve a simpler task first, where we assume that all $$$a_i$$$ and $$$b_i$$$ are positive, and all updates and queries are on the root vertex. We can see that we are looking into maximum $$$\left(x + c_v \right) \cdot d_v$$$ = $$$c_vd_v + xd_v$$$, where $$$x$$$ is the cumulative sum of updates until this point. For a given $$$x$$$, this can be solved in $$$\mathcal O(\log n)$$$ using convex hull trick.
How do we handle negative values of $$$a_i$$$ and $$$b_i$$$? We simply try all the lines $$$-c_vd_v - xd_v$$$ as well.
The second issue is that our updates and queries can occur on arbitrary vertices. We can linearise the tree using DFS – then subtree of a vertex corresponds to an interval in the array. Afterwards, we use sqrt-decomposition in a fairly standard way:
• We partition the array into blocks of size roughly $$$\sqrt n$$$, build a convex hull trick structure on each of them, and remember the value of $$$x$$$ for each of them separately.
• Given an update, some blocks are untouched, in some we just need to update $$$x$$$ in constant time, and there are at most two blocks which are updated partially, which we rebuild from scratch.
• Given a query, we can use the convex hull trick structure to get the maximum in a block that is fully covered by the query. Again, we have at most two blocks that are partially intersected – there we can brute force the maximum.
This yields a $$$\mathcal O(n + q \sqrt n \log n)$$$ algorithm.
Oh wait, you're right. This solution has a rather large constant factor, so let's not stop there. What do we need the $$$\log n$$$ factor for? Two things: sorting all the lines by slope and determining the best line in a convex hull trick structure. Let's get rid of both – firstly, as $$$b_i$$$ doesn't change, we can sort once before processing any queries. Secondly, notice that the updates only add positive values, thus we only ever query lines with increasing $$$x$$$. Hence, no binary search is needed – we can simply advance a pointer over the structure in $$$\mathcal O(1)$$$ amortised. Overall complexity becomes $$$\mathcal O(n \log n + q \sqrt n)$$$. There, no marmots harmed.
One final remark – the cost of building a convex hull structure in a block is slightly higher than that of iterating over the blocks. It seems that the most efficient size of the block is $$$\sqrt{n/6}$$$. This final observation was not needed to get AC.