Sum of sqrt of (size_of_subtree) in tree

Правка en4, от PouyaNavid, 2020-03-26 11:43:02

Hi,

Consider a rooted tree

size(v) = number of vertices in subtree of v

Any good limit on $$$\sum_{i=1}^{n} $$$$$$\sqrt{size(i)}$$$ ?

like

$$$O(n \log n)$$$

$$$O(n \log \log n)$$$

$$$O(n)$$$

...

UPD :

b(v) is a son of v with the largest subtree size.

limit on $$$\sum_{i=1}^{n} $$$$$$\sqrt{size(i) - size(b(i))}$$$

Теги #tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en15 Английский PouyaNavid 2020-05-31 16:32:57 2 Tiny change: '*UPD :**\n\n\n**_b(v' -> '*UPD :**\n \n\n**_b(v'
en14 Английский PouyaNavid 2020-04-03 11:10:46 2 Tiny change: '(i))}$ ?\n' -> '(i))}$ ?\n\n'
en13 Английский PouyaNavid 2020-04-03 11:10:10 1 Tiny change: '\n$O(n)$\n\n...\n \n' -> '\n$O(n)$\n \n...\n \n'
en12 Английский PouyaNavid 2020-04-02 11:24:53 1 Tiny change: '$\n\n...\n\n \n \n**' -> '$\n\n...\n \n \n \n**'
en11 Английский PouyaNavid 2020-03-30 07:47:06 1 Tiny change: 'ted tree\n\n**_size(' -> 'ted tree\n \n**_size('
en10 Английский PouyaNavid 2020-03-29 16:08:34 1 Tiny change: 'n\n...\n\n\n \n**UPD' -> 'n\n...\n\n \n \n**UPD'
en9 Английский PouyaNavid 2020-03-28 20:19:20 1 Tiny change: 'n...\n\n\n\n**UPD :*' -> 'n...\n\n\n \n**UPD :*'
en8 Английский PouyaNavid 2020-03-28 13:14:44 1 Tiny change: 'btree of v\n\nAny go' -> 'btree of v \n\nAny go'
en7 Английский PouyaNavid 2020-03-27 17:32:23 2 Tiny change: '}$ ? \n\nlike\n' -> '}$ ? \n\n\nlike\n'
en6 Английский PouyaNavid 2020-03-27 11:39:22 2 Tiny change: 'n...\n\n\n**UP' -> 'n...\n\n\n\n**UP'
en5 Английский PouyaNavid 2020-03-26 19:38:00 2 Tiny change: 'ze(b(i))}$\n' -> 'ze(b(i))}$ ?\n'
en4 Английский PouyaNavid 2020-03-26 11:43:02 38 Tiny change: 'e\n\n\n$O(N*LOG)$\n\n$O(N' -> 'e\n\n\n$O(n \log)$\n\n$O(N'
en3 Английский PouyaNavid 2020-03-26 10:53:20 134 Tiny change: '\nlimit on($\sum_{i=1' -> '\nlimit on $\sum_{i=1'
en2 Английский PouyaNavid 2020-03-26 10:13:33 2 Tiny change: '**Hi,\n\nCon' -> 'Hi,\n\nCon'
en1 Английский PouyaNavid 2020-03-26 10:13:22 248 Initial revision (published)