I don't usually like to write about problems I've solved, but the solution for the problem 1904F - Beautiful Tree 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 this was to use a segment tree to graph technique mentioned in this blog post, where this problem is mentioned in the comments as well. 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 the range that does.

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' appearance in the topological sort.

I think without examples, topics or solutions can feel a little abstract, so here's an example and how the algorithm solves it:

Input:
5 3
1 2
1 3
2 4
2 5
3 6
3 7
5 8
1 4 3 2
2 7 8 1
1 2 6 6

The input corresponds to this tree:

/predownloaded/d4/a5/d4a50582e3896026091e4dcc58d18efc95648f51.png