PROBLEM LINK:
Author: Sergey Kulik
Tester: Harshil Shah
Editorialist: Pawel Kacprzak
DIFFICULTY:
MEDIUM
PREREQUISITES:
Trees, Union-Find, LCA
PROBLEM:
Given a tree on N nodes and a sequence of N - 1 edge delete operations, for each i = 0, 1, N - 1, find the product of diameters of all trees formed after performing the first i delete operations. In this problem, diameter of a tree is defined by the maximum sum of weights of nodes taken over all simple paths in the tree.
QUICK EXPLANATION:
Compute the required diameters in reverse order, i.e. begin when there are no edges in the set of trees and add edges in the reverse order they are deleted. At each step, for the newly formed tree from two smaller ones, compute its diameter by combining diameter of these smaller trees, and accumulate it to the result sequence. At the end, print the resulting sequence in the reversed order.
EXPLANATION:
In all subtask we are going to use the same approach, the only difference will be in complexity of computing the diameter of newly formed tree.
The general method is the following. Given a sequence of edge delete operations ei1, ei2, …, eiN - 1, we are going to perform these operations in the reversed order. It means that instead of starting with a single tree, we are going to start with N trees consisting of single nodes, and at each step we are going to merge two trees into a bigger one using the edge that is deleted at the corresponding step in the sequence of delete operations. Notice that if before a merge operation, the product of diameters is P and diameters of trees that are going to be merged are DA and DB respectively, and the diameter of the newly formed tree by this merge is DC, then the product of diameters after the merge is P / DA / DB * DC - actually in the problem we want to have this result computed modulo 109 + 7, but it can be easily achieved by representing division as multiplication by modular multiplication inverse modulo 109 + 7. Using this method we will get the resulting sequence of products of diameters in the reverse order. The last thing to do is to reverse that sequence and return it as the result. It remains to show how to compute the diameter DC of the tree formed by the merge of two smaller trees. Each subtask corresponds to a solving this last problem in particular time complexity. Notice that we are going to perform a merge operation O(N) times in each of subtasks.
Subtask 1
In the first subtask we have N ≤ 100, so any method of computing a diameter of newly formed tree with quadratic running time gets the job done. We can even explicitly recompute the set of trees after the merge from the scratch. The easiest method of computing the diameter of a single tree is to perform DFS from each of its nodes to compute the path with maximum weight starting with the selected node and taking maximum of this weights over all nodes. This method will result in O(N3) time, because we are performing O(N) merge operations and each merge along with computation of new diameter takes O(N2) time.
Subtask 2
In the second subtask we have N ≤ 5000, so O(N3) method is definitely too slow. However, merging two trees in O(N) time may be acceptable if it is implemented efficiently (if not union-find can be used as described in the third subtask). So the goal is to compute the diameter of a newly formed tree in O(N) time and this can be done by using a well known, standard linear algorithm using two combined DFS calls: first, from arbitrary node v, we compute the node u for which the path v -> u has the largest weights among all paths starting in v. After that, starting in node u, we compute the node w, for which the path u -> w has the largest weights among all paths starting in u - this weight is the resulting diameter. Since each merge runs in O(N) right now, the total running time is O(N2) which should pass for N ≤ 5000.
Subtask 3
In the last subtask we need a really efficient method of computing the diameter of tree TC formed by merging two smaller trees TA, TB by adding a single edge between them. We are going to perform this merge along with computation of diameter of TC in O(log(N)) time. First, notice that the merge can be done using union-find data structure in O(log(N)) or faster if necessary. So the only remaining thing is to show how to compute the diameter of TC. In order to do it, for each tree ever formed in the computation, we are going to store two endpoints of its diameter (if the tree has only a single node, then these endpoint are the same). The crucial observation is that the diameter of TC can be computed when we know endpoints of diameters of TA and TB. More specifically, diameter of TC is either diameter of TA or diameter of TB or a path between one of endpoints of diameter of TA and one endpoint of diameter of TB. This is easy to show, because if any other path has a larger weight, then diameter of either TA or TB should be larger, which leads to a contradiction. Since diameters of TA and TB are already computed, the only remaining thing is to show how to compute the weight of a paths between endpoints of these two diameters. In order to do that we are going to use LCA tree-data structure, which can be used to compute the length of a path between any two nodes in a tree in O(log(N)) time with O(N * log(N)) time precomputation, which is sufficient here. Thus the total running time is O(N * log(N)), since each merge along with computation of diameter of newly formed tree takes O(log(N)) time. Please refer to author’s and tester’s solutions for implementation details.
AUTHOR’S AND TESTER’S SOLUTIONS:
Tester’s solution can be found here.
Editorialist’s solution can be found here.