Prepared by: Ivan Paljak and Josip Klepec

Setup

Summarization of the task is somehow choosing the ~K~ node labels and then ~K-1~ queries such that they uniquely determine a tree.

(DMOJ editor's note: Go here to read Algorithm 1)

The subset ~S~ of node labels forms a connected subgraph in tree ~T_1~. In tree ~T_2~ it is just some arbitrary subset of nodes.

(DMOJ editor's note: Go here to read Algorithm 2)

Each query may also give some lowest common ancestor which is not in ~S~.

We define ~S_1~ and ~S_2~, a subset of nodes in respective trees, as the union of ~S~ and lowest common ancestors that appear in queries.

Lemma 0.1. ~S_i~ can be formed into a tree structure. Furthermore, ~S_1~ forms a connected subgraph in tree ~T_1~ but it isn't relevant for the rest of the algorithm.

We will describe the algorithm for making such small tree. It can be applied to both ~T_1~ and ~T_2~.

(DMOJ editor's note: Go here to read Algorithm 3)

Now for these trees, we want to reconstruct the weights of edges. For each tree, we have ~2 \times (K-1)~ paths we know the length of. Some may be redundant.

Lemma 0.2. Those paths are such that they uniquely determine the tree.

The proof is not too hard so we won't go into too much detail. Firstly, imagine we construct a graph as described in section for Full Points (see section couple lines below).

Now, all we need to prove is that that graph is connected. There is no need to prove that the given set of queries doesn't give a contradiction because we can rely on the authentication of the interactor.

We can prove the connectivity by analyzing how we constructed the queries. The connectivity becomes very obvious very quickly after we realize that we first sorted the node labels and then asked of adjacent ones. Every pair of adjacent node labels being connected means the whole set is.

Subtask 3

Even though it is not necessary for full points we can use Gaussian elimination to solve this subtask. Every query forms some equation (with variables being edge weights in respective trees). Now we get two linear systems, one for each tree and we just solve each independently.

https://cp-algorithms.com/linear_algebra/linear-system-gauss.html

Subtask 4

It is not hard to modify the algorithm for constructing the small tree to reconstruct the weights as well if our queries are also sorted by the preorder. But it only holds for the second tree. To achieve this for both trees we need to find a set of node labels such that they can be ordered in a way that they form a monotonic sequence with respect to the preorder in the first tree, but also in the second tree.

One could always choose such a subset because ~K^2 \le N~ holds.

If we order node labels with respect to preorder in tree ~T_1~ and look at the sequence of their preordering positions in the tree ~T_2~. We can find a monotonic subsequence of length ~K~.

Theorem 0.3 (Erdos-Szekeres). For given positive natural numbers ~s, r~, any sequence of distinct real numbers whose length is at least ~N = sr+1~ contains a monotonically increasing subsequence of length ~s+1~ or a monotonically decreasing subsequence of length ~r+1~ (or both).

Full Points

Method 1

For a rooted tree we denote ~d(x)~ as the length of the path that starts at the root of the tree and ends at ~x~.

Then our queries give equations of the form:

$$\displaystyle d(x_i)-d(y_i) = w_i$$

Now, we construct a weighted directed graph by adding an edge from ~y_i~ to ~x_i~ with weight ~w_i~ and a reverse edge with negative weight ~-w_i~.

Now to find ~d(x)~, we just find the length of the path from the root to ~x~ in our new graph using dfs. Such a path is guaranteed to exist because of the structure of queries.

When we reconstructed ~d(x)~ for every ~x~ it is easy to output the answers.

This gives us an algorithm with complexity ~\mathcal O(K + N \log N)~.

Method 2

Alternatively, one could solve the system of equations by using Gaussian elimination faster by observing that each equation forms a path in a tree. Furthermore, a path goes from some node to the root of the tree (meaning lca of endpoints of the path is always on them).

(DMOJ editor's note: Go here to read Algorithm 4)

At first, this gives us complexity ~\mathcal O(K^2 + N \log N)~, but it can be sped up to ~\mathcal O(K \log^2 K + N \log N)~ by keeping the set of equations that begin at every node and merging those sets when subtraction equations. If we merge the two sets such that we move everything from smaller set to larger we get the desired complexity. It is convenient to keep equations in stl Set structure to get the minimum path.