I went through this editorial but didn’t get much out of it. I am confused about how he merges two components and initialise the m1 and m2 in components in the beginning. Please help me understand this editorial.
I didn’t read the editorial, but I had some ideas of my own.
Obviously, each bank branch decomposes the tree into some connection blocks.
So for a point of query, the city it wants to go to must be the second largest city in other connection blocks.
The problem becomes the problem of maintaining the maximum and sub-maximum values of some sets.
The only difficulty is that every branch is added, the connection block will continue to be divided, which makes maintenance extremely difficult.
We can use the offline algorithm to maintain these sets from the back to the front, so every branch added is actually subtracted from one branch. When the number of branches of a point is reduced to zero, it is time for some sets to be merged.
DSU can maintains these information of sets.
If these are any mistakes, please contact me.
1 Like
I have already understood these things from the editorial, what I want to know is how he is intialising m1 and m2 in the beginning for every node and how the merging of two components happens.
I think you can read the code once, because it’s really simple.