Minimum distance of a node in tree where more source nodes are added in queries

N=10^5 nodes and E = n-1 edges in a tree.there are Q = 10^5 queries.
Initially node 1 is source node.
source set = { 1 } where distance d = 0.

in each query two integer : type V

two type of queries :

type=2 : add node V to sources set
type=1 : print minimum distance to reach at v from among the sources.

input format :

first line : N{no of nodes} Q{no of queries}

next n-1 lines a b represents bidirectional edges between a to b node.

next Q lines have two integer TYPE V each.

TYPE = 1 or 2

test data :

6 4

1 2

1 3

2 4

2 5

3 6

1 4

1 6

2 2

1 4

Output :




Any O(NlogQ) or O(NlogN)??? thanks in advance :slight_smile:

Keep the follwing data updated during insertions: The minimum distance of a node to v a source node in the subtree rooted at v. To update you will have to update nodes on the path from the new source node to the root. For the query you also have to check the nodes on the path up to root and compare appropriately.

This will work for all but very unbalanced trees. If you still TLE you have to use for example a heavy-light-decomposition.

1 Like

This can be solved with Centroid Decomposition of the tree

It takes O(NlogN) for decomposing tree and O(log^2N) for each query

For more information about this technique, read this awesome article by Tanuj Khattar : Centroid Decomposition of a Tree

1 Like

Focus 3 “wild cupboard decoration” According to authoritative statistics, in August 2009, “the cabinet wild decoration” with “cheap temptation” invaded cupboard domestic market how to build floating deck on concrete patio nearly 40% market share. This data is disclosed, immediately attracted the attention of brand cabinets. To combat the “wild cupboard decoration,” to restore this part of the formal business of the market, while meeting consumer demand for “cheap”, the domestic brand cabinets have strengthened the industrialization, large-scale production, reduce costs, in order to suppress the "wild cupboard decoration .

" It is reported that in 2009 the EU to send cabinet in the original production line imported from Germany on the heroic, once again spending huge sums to more than 800 million paint production line imported from Italy, and with the world hardware giant Blum reached a strategic Interlocking Plastic Wall and Ceiling Sandwich Pan cooperation, through the organization of a special cabinet design competition, raise domestic cabinet industry design standards, etc. to enhance the competitiveness of enterprises. Bound Compression “wild cupboard decoration” living space, and ultimately play a role in purifying the cabinet market. Kitchen standard four residential focus this year on October 1 officially implemented in the construction industry, “Residential Kitchen” industry standards, standardized kitchen building space requests, for the future kitchen units only 22 choices.

This makes large-scale cabinet industry, standardization, industrial production possible, but also for market expansion cabinet companies provided the conditions. On the one hand, frequent measurement, design and other issues before the differences due to different kitchen units and cupboards itself individual needs arising will be greatly improved, long-distance outdoor composite railings for stairs supply cabinet enterprises will become more simple; on the other hand, for the EU to send , Section Po brand cabinets and other enterprises, standardization, industrial production will further reduce production costs, not only enables companies have become more competitive, but also to the brand’s cabinet has more potential consumer groups, in order to enter new The market offers greater possibilities.

Maybe you can do an “Offline Query Processing”…by taking all the inputs first and insert all the source nodes to your set and then pre-processing the distances.This is just a rough idea.

How do you augment the centroid decomposition in order to compute the distance to the (growing) source set?

Initially consider the distances to be Infinity, Now start adding the elements of source set one by one by updating the ancestors in centroid tree