Editorial for A New Tree

Observation: Look at the special property of this tree. If I select any range of edges, I will get a tree. So in between each pair of consecutive edges there will be a common node. That's why the shape of the tree will be like a long chain with some single nodes connected to it.

Solution 1: Build the tree and find the longest chain. Whenever a query (X, Y) comes, find the first and last edge between Xth and Yth edge which are part of the longest chain. The edges in the longest chain will surely contribute to the answer. Now we have to check if the first and last node has some single node connected to it or not.

Solution 2: Let UX, VX are the nodes in Xth edge and UY, VY are the nodes in Yth edge. The diameter will be either of these 4 pairs (UX, UY) , (UX, VY), (VX, UY), (VX, VY).

Time Complexity: O(Q × log N)


    85% Solution Ratio

    EgorKulikovEarliest, Mar '20

    mahdi.hasnatFastest, 0.2s

    mahdi.hasnatLightest, 7.1 MB

    serotoninShortest, 733B

    Toph uses cookies. By continuing you agree to our Cookie Policy.