In centroid decomposition say we do a work of O(n) per centroid tree then we get a time complexity of O(nlgn) because of the HP n + 2*n/2 + 4*n/4 + .. which comes out to n + n + n + ... lgn times. But if I traverse a fixed array of size 100000 for every centoid tree then will the complexity become 10^5 + 2*10^5 + .... ? which would be (1 + 2 + 3 + .. lgn)10^5
Is this analysis correct? And how to avoid the problem of tle if it arises (is using map useful for such cases?)
Well, assuming n = 100000 is the number of nodes, the complexity would be O(n2), since you have n centroid trees — one for each node.