[Problem proposal] Vertex Add Range Contour Max on Tree

[lrvideckis]

Problem name: Vertex Add Range Contour Max on Tree

Problem

Given a tree with N vertices, where the i-th edge connects vertices ui​ and vi​. Value ai​ is written on the vertex i. Process the following Q queries in order:

• 0 p x: a[p]​←a[p]​+x
• 1 p l r: Print the max of the values written on the vertices whose distance from the vertex p is in [l,r).

Constraint

same as https://judge.yosupo.jp/problem/vertex_add_range_contour_sum_on_tree

Solution / Reference

edge centroid decomposition

https://codeforces.com/blog/entry/104997 https://codeforces.com/blog/entry/120446

(Optional) Note / Disucussion

edge CD is possible in O(n log^2 n): there's only 2 childs in each decomposition, so you just query the [l,r) range in the other child

https://github.com/programming-team-code/programming_team_code/blob/main/trees/edge_centroid_decomp/contour_range_query.hpp

normal CD is possible in O(n log^3 n) with like a 2d structure like mergesort/wavelet tree to handle querying all childs in suffix, and of certain depth range

[cameroncuster]

dang this is clean ^^^

[noshi91]

Edge CD was previously discussed when the sum version was added, and it was concluded that the sum version is better for checking the correctness of not only normal CD but also edge CD. see https://github.com/yosupo06/library-checker-problems/issues/816 (I'm sorry for the conversation being in Japanese.)