E. Strange device
binary search; interactive; math; trees
It is an interactive problem.Vasya enjoys solving quizzes. He found a strange device and wants to know how it works.This device encrypted with the tree (connected undirected graph without cycles) with \(n\) vertices, numbered with integers from \(1\) to \(n\). To solve this quiz you should guess this tree.Fortunately, this device can make one operation, using which you should guess the cipher. You can give the device an array \(d_1, d_2, \ldots, d_n\) of non-negative integers. On the device, there are \(n\) lamps, \(i\)-th of them is connected with \(i\)-th vertex of the tree. For all \(i\) the light will turn on the \(i\)-th lamp, if there exist such vertex of the tree with number \(j \neq i\) that \(dist(i, j) \leq d_j\). Let's define \(dist(i, j)\) as the distance between vertices \(i\) and \(j\) in tree or number of edges on the simple path between vertices \(i\) and \(j\).Vasya wants to solve this quiz using \(\leq 80\) operations with the device and guess the tree. Help him!
It is a picture of the tree which encrypt the device from the first test: It is a table of pairwise distances between vertices in this tree: If you make operation where \(d = [0, 0, 0, 0, 0]\), no lamp will switch on, because \(dist(i, j) > 0\) for all \(i \neq j\). If you make operation where \(d = [1, 1, 2, 0, 2]\), all lamps except the lamp connected with the \(3\)-rd vertex will switch on. For example, lamp connected with the \(1\)-st vertex will switch on, because \(dist(1, 5) = 1 \leq 2 = d_5\). If you make operation where \(d = [0, 0, 0, 1, 0]\), all lamps except lamps connected with the \(4\)-th and \(5\)-th vertices will switch on. If you make operation where \(d = [0, 1, 0, 0, 1]\), only lamps connected with the \(1\)-st and \(4\)-th vertices will switch on.