Solution to CCF WC2018 Task 1, in English

Правка en3, от 3tao1n, 2018-03-15 09:51:47

This article is about the solution to a recent problem from the CCF NOI 2018 Winter Camp, the penultimate stage before the Chinese national team is selected. I believe that the solution contains a few techniques that are rarely known.

Short description of the problem:

You are given three trees T1, T2, T3 with the same number of nodes. Let d1(x, y), d2(x, y), d3(x, y)​ denote the distance from x to y in each tree. Find a pair of nodes (x, y)​ such that d1(x, y) + d2(x, y) + d3(x, y)​ is maximized. Output that value.

Let's start by solving the problem for two trees only. Let f1(v) denote the distance from node 1 to node v in the first tree. We want to maximize . For each node v in the second tree, let's add a node v' and an edge (v, v') to the second tree, with weight f1(v). If we fix , we have reduced our problem to this: "Given two sets of nodes A, B, merge them and calculate the maximum value of , where d'2(a, b) denotes the distance between a and b in the modified second tree." It can be proven through a reductio ad absurdum argument, that for each one of these sets, we only need to store a single pair of nodes (a, b) such that d'2(a, b) is maximized. This means that merging is done in this way: Let (a1, b1) and (a2, b2) be the aforementioned pairs. The value of the new pair will be (a1, a2), (a1, b1), (a1, b2), (a2, b1), (a2, b2),  or (b1, b2), depending on which pair maximizes d'2(a, b). This gives us an algorithm.

Now, let's solve another version of the problem: We have three trees, but the second and third trees are path-shaped. Again, let's fix . We have to maximize f1(x) + f1(y) + |f2(x) - f2(y)| + |f3(x) - f3(y)|. For each subtree of the first tree, we will maintain four values:

  • .

Since , the best answer will be either equal to g1, 1(x) + g2, 2(y) or g1, 2(x) + g2, 1(y) for some pair of nodes (x, y). This gives us a simple O(n) solution if we keep the prefix and suffix maxima of g for the children of every node.

Unfortunately, we still have one more subtask to solve before we reach the full solution. In this subtask, we are given two trees and a path. Let's start by introducing the auxiliary tree: Let A be a subset of nodes of a tree T. Then, the auxiliary tree contains the nodes , and every node is connected to its closest ancestor in the original tree with an edge of weight . The auxiliary tree therefore has O(|A|) nodes. Now, we can do D&C on the path: Let's fix its midpoint m. We have to maximize d1(x, y) + d2(x, y) + d3(x, m) + d3(m, y), where x ≤ m and y ≥ m. If we add an extra vertex v' to T2 where the weight of the edge (v, v') is equal to d3(v, m) and create the auxiliary trees that only contain the vertices in the range we're currently processing, we can use the solution to the "two trees" subtask to solve this one too. This gives us an solution, with an albeit difficult implementation.

And finally, we can move on to the complete solution. But first, we have to introduce another technique, called "centroid decomposition on edges". Here is a simple pseudocode description of this technique:

Centroid decomposition on edges code

Obviously, this will work in O(n2) in some cases, e.g. a star graph. However, if we have a binary tree, this code works in O(nlogn). We can make an arbitrary tree binary while preserving distances between nodes using a method similar to the left-child right-sibling conversion. If we have a node with k > 2 children, we are going to attach a single child node to it. This node's left child will be the former first child of the node, and it will be connected to it with a weight of identical edge. Its right child will be its "sibling" node, whose left child will be the former second child of the node, and so on.

Our full solution is simply a combination of these two techniques. Make the first tree binary, and do "centroid decomposition on edges" on it. Similarly to the previous subtask, add a dummy node x', such that d'2(x, x') = h(x), where h(x) is the distance from node x to the active edge in the first tree. Then, solve the "two trees" subtask. This gives us an solution.


This article was written by f2lk6wf90d, based on our chat on Telegram. Thank you for your awesome work, Martin!

If you find any mistakes in this solution, comments are welcomed.

Теги advanced data structure, centroid decomposition, china, dp on trees

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский 3tao1n 2018-03-15 13:21:37 14 fix photo
en5 Английский 3tao1n 2018-03-15 11:08:16 10 Change incorrect name
en4 Английский 3tao1n 2018-03-15 09:52:25 18 new title
en3 Английский 3tao1n 2018-03-15 09:51:47 6 new title
en2 Английский 3tao1n 2018-03-15 09:51:04 0 (published)
en1 Английский 3tao1n 2018-03-15 09:50:40 5389 Initial revision (saved to drafts)