Task
You are given a tree with $$$n$$$ vertices, the number $$$a_v$$$ is written in vertex $$$v$$$. There are two types of queries:
- Find the maximum number on the shortest path from vertex $$$u$$$ to vertex $$$v$$$.
- Set $$$a_v = x$$$.
Solutions
This is a very well-known problem, so you've probably come up with a solution using Heavy-Light Decompositon (or Link-Cut Tree, if you're a big fan of splay trees). The first variant has an asymptotics of $$$O(log^2~n)$$$ per query in the standard implementation, the second has $$$O(log~n)$$$, but you need more specific knowledge to use it. It would be nice to achieve better HLD asymptotics using some simple ideas. It turns out that this is possible.
$$$O(log^2~n)$$$ per query
Let's try to decompose the tree into disjoint paths, so that when we get a query we need to split the path between vertices from the query into a small number of segments so that each of them lies in some single path.
We call an edge heavy if it connects a vertex to its child subtree with the largest size (if there are several such edges, we choose any of them), the other edges will be considered light. If any two heavy edges have a common vertex, we will merge them into one path. As a result, we will decompose the tree into paths consisting of heavy edges (it is easy to understand that such paths cannot intersect due to the definition of a heavy edge).
Let us show that any vertical path can be divided into $$$O(log~n)$$$ parts, each of which lies entirely in one path. Let's go from the bottom vertex upwards. If we have changed the current decomposition path, it means that we have moved along the light edge, which means that the size of the subtree we are now in has increased by at least $$$2$$$ times. Since there are at most n vertices in the tree, we can't change the path more than $$$log~n$$$ times. So we have achieved what we wanted.
Now, to answer the query, it is enough to find out the maximum on the paths $$$(lca(u, v), u)$$$ and $$$(lca(u, v), v)$$$. This can be done, for example, using a segment tree (hence $$$O(log^2~n)$$$).
To change $$$a_v$$$, you need to make one update in the segment tree.
We won't look at standard HLD implementation in this post, because there are people who will do it better than me.
$$$O(log~ n)$$$ per query
To prove the asymptotics in the previous paragraph, we used the fact that going from one path to another, the subtree increases by at least $$$2$$$ times. By developing this idea, we can achieve better asymptotics.
What if we try to create a data structure such that taking a maximum on some segment of the path at each of its operations increases some value $$$\le n$$$ by at least a factor of $$$2$$$? Then we would get what we wanted.
The main problem lies in the segment tree. The asymptotics of finding the maximum on a segment is $$$O(log~n)$$$ (or $$$O(log~(r - l))$$$, depending on the implementation). This is because we divide the current segment in half without considering the size of the subtrees in any way. Let's fix this. To do this, we need to use another binary tree instead of the segment tree.
Consider some decomposition path $$$v_1, v_2, \dots, v_k$$$. Let us temporarily remove edges between neighboring vertices, and by $$$w_i$$$ denote the size of the subtree $$$v_i$$$ that remains after removing edges. Let $$$W = \sum_{i=1}^{k} w_i$$$. Let us find the first index $$$j$$$ such that $$$\sum_{i=1}^{j} w_i \ge \frac{W}{2}$$$. Let's make vertex $$$v_j$$$ the root of our binary tree, and recursively run from the left and right halves of the path to determine the left and right child. Now we know how to build some strange tree, but it is not clear how it is better than a segment tree.
First, let us consider how to answer the maximum on a segment in such a tree. To do this, let us look at the vertices of the path, which are the leftmost and rightmost vertices of the segment ($$$l$$$ and $$$r$$$) on which we need to calculate the maximum. Let's find their position in the tree we have constructed. Now, to answer the query, we need to go up from $$$l$$$ to $$$lca(l, r)$$$ in our tree, updating the answer through the value of the current vertex, as well as the value of its right subtree if the vertex itself is a left child. Similarly, we need to go up from $$$r$$$.
It remains to calculate the asymptotics. If we look at the $$$\sum w_i$$$ in the current subtree of our data structure, by virtue of the construction of the tree, it increases by at least a factor of $$$2$$$ when we go to the ancestor. Then if we keep track of this value, we can realize that we have achieved $$$O(log~n)$$$ per query, because if we go up when answering a query in the current path, this value increases by at least a factor of $$$2$$$, and if we go to an light edge, $$$\sum w_i$$$ doubles again (now because of the original path decomposition). It turns out that we have achieved what we wanted (it is pretty obvious that this value cannot exceed $$$n$$$).
To update $$$a_v$$$, we need to take the desired vertex in the binary tree built on the path and update all its ancestors (the proof of the asymptotics is similar).
For a better understanding, I recommend reading the code:
It is clear that this is not the kind of code you want to write at the olympiad, but I think it is always interesting to learn new things.
PS
Don't judge strictly, this is my first post on such topics. If you notice a typo somewhere, please let me know.
I want to say thanks to my friends who helped me to find information about this modification.
It also seems to me that mass modification operations can be done on this structure.
PS 2
I apologize for my bad English
