Subtask 1

For the first subtask, we can depth first search / breadth first search for each of the updates and queries and update/query the values in the depth range.

Time Complexity: ~\mathcal{O}(NQ)~

Subtask 2

For the second subtask, we can treat the graph as an array and use two segment trees that support range increments and sum queries with lazy propagation. Let ~A[i]~ be the value of each vertex. The first segment tree will support range updates and queries for ~\sum_{i = l}^r A[i] \times i~, while the second segment tree will support range updates and queries for ~\sum_{i = l}^r A[i]~. To update an interval, we will update the first segment tree with the value ~c~. However, we have added ~\sum_{i = l}^r c \times i~, when we really want ~\sum_{i = l}^r c \times (i - l)~. To correct this, we can see that the term ~c \times -l~ is constant, so we can update the second segment tree with this value.

Time Complexity: ~\mathcal{O}(N + Q \log N)~

Subtask 3

For the third subtask, the question is asking us to perform operation in the subtree of ~u~. We can flatten the tree with an Euler tour, and reindexing vertices based on their preorder traversal index. For each subgraph, we will maintain two segment trees that support range increment and sum queries with lazy propagation. The first segment tree will support range updates and queries for ~\sum_{i = l}^r A[i] \times d(i)~, where ~d(i)~ is the depth of vertex ~i~, while the second segment tree will support range updates and queries for ~\sum_{i = l}^r A[i]~. To update or query the subtree of ~u~, we will look at the range ~[st_u, en_u]~, where ~st_u~ is the preorder index of ~u~ and ~en_u~ is the maximum preorder index in the subtree of ~u~. For updates, we can use a method similar to subtask 2.

Time Complexity: ~\mathcal{O}(N + Q \log N)~

Subtask 4

For the fourth subtask, we can treat the graph as an array, indexed based on the order of vertices sorted in non-decreasing order of depth, and use a segment tree that supports range updates and queries for ~\sum_{i = l}^r A[i] \times d(i)~, where ~A[i]~ is the value of the vertex, ~l~ is the minimum index with depth ~a~, and ~r~ is the maximum index with depth ~b~.

Time Complexity: ~\mathcal{O}(N + Q \log N)~

Subtask 5

For the fifth subtask, we will divide the tree into "fragments". A fragment is a set of vertices such that the edges between each vertex in the fragment and its parent form a connected subgraph.

One way to do this is to iterate through the vertices in non-increasing order of depth. For each vertex, we will go through its adjacency list and add the size of each child to a sum. If this sum goes over ~B~ (which will be determined later), we will create a fragment containing all vertices in the subtrees of the children in the adjacency list up to and including the current child. Decrement the size, and continue going through the remaining children in a similar manner. There is also a way to build this using depth first search.

There will be around ~\frac{N}{B}~ fragments in total. For a subtree of a vertex, it can be shown that there is at most one subgraph that has some vertices inside the subtree, and some vertices outside the subtree. All other fragments will either have all of its vertices inside the subtree, or all of its vertices outside the subtree.

For each subgraph, we will maintain two segment trees that support range increment and sum queries with lazy propagation. These segment trees will be indexed based on the order of vertices in the subgraph sorted in non-decreasing order of depth, similar to subtask 4. Let ~A[i]~ be the value of vertex ~i~. The first segment tree will support range updates and queries for ~\sum_{i = l}^r A[i] \times d(i)~, where ~d(i)~ is the depth of vertex ~i~, while the second segment tree will support range updates and queries for ~\sum_{i = l}^r A[i]~.

To handle updates, first we will go through all the vertices in the subgraph of ~u~, and update the value in the segment tree for vertices that are in the subtree of ~u~ with depths between ~a~ and ~b~. Checking if a vertex is in the subtree of ~u~ can be done similar to subtask 3, by flattening the tree with an Euler tour. Since there are ~B~ vertices in the subgraph with segment tree updates taking ~\mathcal{O}(\log B)~ time, this will take ~\mathcal{O}(Q B \log B)~ time in total. One optimization is to propagate all the values in the segment tree to the leaves, collect the values at the leaves into a single array, and update the array instead of the segment tree. We can then rebuild the segment tree after all the updates in the subgraph, which will take ~\mathcal{O}(QB)~ time in total. Afterwards, we can go through all the fragments and update the segment trees of the fragments in the subtree of ~u~. Note that it may be the case that only part (or none) of the range of the depths for that subgraph intersects the range ~[a, b]~. Updating the segment tree can be done similarly to subtask 2. This will take ~\mathcal{O}(Q \times \frac{N}{B} \times \log B)~ time in total.

Queries can be handled in a similar fashion, by first checking the vertices of the subgraph that is partially in the subtree of ~u~, before querying the fragments that are fully in the subtree of ~u~. The time complexity is the same as updates.

Here, it is optimal to choose ~B = \sqrt{N \log N}~.

Time Complexity: ~\mathcal{O}(N + Q \sqrt{N \log N})~