conceptual question in centroid decomposition

Правка en1, от purple_dreams, 2018-04-10 02:52:01

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?)

Теги centroid decomposition

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский purple_dreams 2018-04-10 02:52:01 524 Initial revision (published)