I don't usually like to write about things I've done on Codeforces (in fact I have written a post once before), but the solution for the problem 1904F - Прекрасное дерево I really liked. So, here's how I solved it.
Problem Overview
You have a tree of $$$n$$$ nodes, and your job is to assign a unique value between $$$1$$$ and $$$n$$$ to each node so that it fulfills $$$m$$$ conditions of two types:
Type $$$1-$$$ On the path from node $$$a$$$ to node $$$b$$$, node $$$c$$$ has to have the minimum value.
Type $$$2-$$$ On the path from node $$$a$$$ to node $$$b$$$, node $$$c$$$ has to have the maximum value.
How do we assign values to the tree so that all conditions are satisfied?
Idea 1:
My initial idea was to do topological sorting on the tree some way, but no method was visible at first. We could assign edges between nodes so that for each edge from $$$u$$$ to $$$v$$$, $$$u \lt v$$$. But when we assign each edge individually, this would have a complexity of $$$O(n \cdot m)$$$, which would exceed the time limit.
Idea 2:
My solution for that was to use a segment tree to graph technique mentioned in this blog post, where coincidentally, this problem was mentioned in the comments. We can construct a segment tree on a compression of the tree in order to handle the conditions, but how would we find paths of the tree in this compression?
Idea 3:
An Euler tour of the tree wouldn't work, since paths of the tree aren't subsequent within the compressed array. Rather, we would have to use heavy-light decomposition to handle the queries. So, for each query, we can go up to the $$$LCA$$$ of nodes $$$a$$$ and $$$b$$$, and for each heavy path on the way, we can do range edge assignments. One caveat with this is that we need to not assign an edge between any range that includes $$$c$$$, and $$$c$$$ itself, so we need to divide any range that would.
Final Solution:
We first do heavy-light decomposition on the tree, to get an array where nodes along heavy paths are subsequent. Next, we can build a segment tree graph on this array. We can then add range edges for each of the conditions, to then do topological sorting on. The values can then be assigned from the order of the leaf nodes of the segment tree's appearance in the topological sort.
Final time complexity is $$$O(m \log^2 n)$$$, because we have $$$m$$$ edge operations taking $$$\log n$$$ time for each heavy path, which there are a maximum $$$\log n$$$ of on a simple path. Although, in practice, it is faster.
However, I think that without examples, topics or solutions can feel a little abstract, so here's one and how the algorithm solves it.
Example:
Input:
5 3
1 2
1 4
2 3
2 5
4 6
4 7
5 8
1 4 3 2
2 7 8 1
1 2 6 6
The input corresponds to this tree:
Here, the heavy paths are $$$7; 6 \rightarrow 4; 3; 8 \rightarrow 5 \rightarrow 2 \rightarrow 1$$$. Thus the compressed array we get is $$$[7, 6, 4, 3, 8, 5, 2, 1]$$$. Then from this, we can build a segment tree graph which looks like this:
For the first condition, we need to add edges $$$2 \rightarrow [2,1]; 2 \rightarrow 3; 2 \rightarrow 4$$$. Since we need to exclude $$$2$$$ from the first edge, it becomes $$$2 \rightarrow 1$$$.
For the second condition, we need to add edges $$$7 \rightarrow 1; 4 \rightarrow 1; [8,5,2,1] \rightarrow 1$$$. Again, we need to exclude $$$1$$$ from the last range, which becomes $$$[8,5,2] \rightarrow 1$$$.
For the last condition, we need to add edges $$$6 \rightarrow [2,1]; 6 \rightarrow 4$$$.
After these edge additions, the graph looks like the following:
Here, each edge's color represents in which update it was added. Also, if you don't understand how these edges are being added, please take a look at the blog mentioned above.
Finally, we can do topological sorting on the graph. The order in which each leaf of the segment tree graph appears is $$$7,6,8,5,2,4,3,1$$$. This means we can assign $$$1$$$ to $$$7$$$, $$$2$$$ to $$$6$$$, and so on; which means we can output $$$8,5,7,6,4,2,1,3$$$.
Note:
I know that this implementation is neither the most efficient nor the fastest to write, but after learning about representing range edge additions on a segment tree graph, it was the most intuitive.
I hope you learned something, or at least enjoyed looking into this problem.
